klisp

an open source interpreter for the Kernel Programming Language.
git clone http://git.hanabi.in/repos/klisp.git
Log | Files | Refs | README

commit f79e0d0b552a9e7c3e4b6b9efa1073cf8f22fd91
parent 9f47db702daf8a966db4c81554e013062bcbdd48
Author: Andres Navarro <canavarro82@gmail.com>
Date:   Wed, 27 Apr 2011 18:53:26 -0300

Merged branch imrat. Rational numbers support is complete.

Diffstat:
Msrc/Makefile | 23++++++++++++++---------
Msrc/imrat.c | 1256++++++++++++++++++++++++++++++++++++++++---------------------------------------
Msrc/imrat.h | 14+++++++++-----
Msrc/kgc.c | 13++++++++++---
Msrc/kgeqp.h | 9+++++++--
Msrc/kghelpers.c | 57+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Msrc/kghelpers.h | 4++++
Msrc/kgnumbers.c | 746+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------------------
Msrc/kgnumbers.h | 32+++++++++++++++++++++++++++-----
Msrc/kground.c | 54++++++++++++++++++++++++++++++++++++++++--------------
Msrc/kinteger.c | 104++++++++++++++++++++++++++++---------------------------------------------------
Msrc/kinteger.h | 44+++++++++++++++++++++++++++++++++++++-------
Msrc/kobject.h | 6++++--
Asrc/krational.c | 671+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/krational.h | 172+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Msrc/ktoken.c | 120++++++++++++++++++++++++++-----------------------------------------------------
Msrc/kwrite.c | 49+++++++++++++++++++++++++++----------------------
17 files changed, 2356 insertions(+), 1018 deletions(-)

diff --git a/src/Makefile b/src/Makefile @@ -10,12 +10,13 @@ MYLIBS= CORE_O= kobject.o ktoken.o kpair.o kstring.o ksymbol.o kread.o \ kwrite.o kstate.o kmem.o kerror.o kauxlib.o kenvironment.o \ kcontinuation.o koperative.o kapplicative.o keval.o krepl.o \ - kencapsulation.o kpromise.o kport.o kinteger.o ktable.o \ + kencapsulation.o kpromise.o kport.o kinteger.o krational.o \ + ktable.o kgc.o imath.o imrat.o \ kground.o kghelpers.o kgbooleans.o kgeqp.o kgequalp.o \ kgsymbols.o kgcontrol.o kgpairs_lists.o kgpair_mut.o kgenvironments.o \ kgenv_mut.o kgcombiners.o kgcontinuations.o kgencapsulations.o \ kgpromises.o kgkd_vars.o kgks_vars.o kgports.o kgchars.o kgnumbers.o \ - kgstrings.o imath.o kgc.o + kgstrings.o KRN_T= klisp KRN_O= klisp.o @@ -44,9 +45,11 @@ klisp.o: klisp.c klisp.h kobject.h kread.h kwrite.h klimits.h kstate.h kmem.h \ kapplicative.h koperative.h keval.h krepl.h kground.h kobject.o: kobject.c kobject.h klimits.h klispconf.h ktoken.o: ktoken.c ktoken.h kobject.h kstate.h kpair.h kstring.h ksymbol.h \ - kerror.h klisp.h kinteger.h kport.h + kerror.h klisp.h kinteger.h krational.h kport.h kinteger.o: kinteger.c kinteger.h kobject.h kstate.h kmem.h klisp.h imath.h \ kgc.h +krational.o: krational.c krational.h kinteger.h kobject.h kstate.h kmem.h klisp.h \ + imrat.h kgc.h kpair.o: kpair.c kpair.h kobject.h kstate.h kmem.h klisp.h kgc.h kstring.o: kstring.c kstring.h kobject.h kstate.h kmem.h klisp.h kgc.h # XXX: kpair.h because of use of list as symbol table @@ -55,11 +58,12 @@ ksymbol.o: ksymbol.c ksymbol.h kobject.h kpair.h kstring.h kstate.h kmem.h \ kread.o: kread.c kread.h kobject.h ktoken.h kpair.h kstate.h kerror.h klisp.h \ kport.h ktable.h klispconf.h kwrite.o: kwrite.c kwrite.h kobject.h kpair.h kstring.h kstate.h kerror.h \ - klisp.h kport.h kinteger.h ktable.h klispconf.h + klisp.h kport.h kinteger.h krational.h ktable.h klispconf.h +# XXX: now that all dealloc code is in gc, many of these are unnecessary kstate.o: kstate.c kstate.h klisp.h kobject.h kmem.h kstring.h klisp.h \ kenvironment.h kpair.h keval.h koperative.h kground.h \ krepl.h kcontinuation.h kapplicative.h kport.h ksymbol.h kport.h \ - kstring.h kinteger.h kgc.h klimits.h ktable.h klispconf.h + kstring.h kinteger.h krational.h kgc.h klimits.h ktable.h klispconf.h kmem.o: kmem.c kmem.h klisp.h kerror.h klisp.h kstate.h kgc.h klispconf.h kerror.o: kerror.c kerror.h klisp.h kstate.h klisp.h kmem.h kstring.h kpair.h kauxlib.o: kauxlib.c kauxlib.h klisp.h kstate.h klisp.h @@ -97,7 +101,7 @@ kgbooleans.o: kgbooleans.c kgbooleans.c kghelpers.h kstate.h klisp.h \ kobject.h kerror.h kpair.h kcontinuation.h ksymbol.h kgeqp.o: kgeqp.c kgeqp.c kghelpers.h kstate.h klisp.h \ kobject.h kerror.h kpair.h kcontinuation.h kapplicative.h \ - kinteger.h + kinteger.h krational.h kgequalp.o: kgequalp.c kgequalp.c kghelpers.h kstate.h klisp.h \ kobject.h kerror.h kpair.h kcontinuation.h kgeqp.h kstring.h kgsymbols.o: kgsymbols.c kgsymbols.c kghelpers.h kstate.h klisp.h \ @@ -141,10 +145,11 @@ kgchars.o: kgchars.c kgchars.h kghelpers.h kstate.h klisp.h \ kobject.h kerror.h kapplicative.h koperative.h kcontinuation.h kgnumbers.o: kgnumbers.c kgnumbers.h kghelpers.h kstate.h klisp.h \ kobject.h kerror.h kapplicative.h koperative.h kcontinuation.h \ - ksymbol.h kinteger.h + ksymbol.h kinteger.h krational.h kgstrings.o: kgstrings.c kgstrings.h kghelpers.h kstate.h klisp.h \ kobject.h kerror.h kapplicative.h koperative.h kcontinuation.h \ kstring.h ksymbol.h kgnumbers.h imath.o: kobject.h kstate.h kmem.h kerror.h -kgc.o: kgc.c kgc.h kobject.h kmem.h kstate.h kport.h imath.h ktable.h \ - kstring.h +imrath.o: kobject.h kstate.h kmem.h kerror.h +kgc.o: kgc.c kgc.h kobject.h kmem.h kstate.h kport.h imath.h imrat.h \ + ktable.h kstring.h diff --git a/src/imrat.c b/src/imrat.c @@ -26,8 +26,8 @@ /* {{{ Useful macros */ #define TEMP(K) (temp + (K)) -#define SETUP(E, C) \ -do{if((res = (E)) != MP_OK) goto CLEANUP; ++(C);}while(0) +#define SETUP(E, C) \ + do{if((res = (E)) != MP_OK) goto CLEANUP; ++(C);}while(0) /* Argument checking: Use CHECK() where a return value is required; NRCHECK() elsewhere */ @@ -39,130 +39,132 @@ do{if((res = (E)) != MP_OK) goto CLEANUP; ++(C);}while(0) /* Reduce the given rational, in place, to lowest terms and canonical form. Zero is represented as 0/1, one as 1/1. Signs are adjusted so that the sign of the numerator is definitive. */ -static mp_result s_rat_reduce(mp_rat r); +static mp_result s_rat_reduce(klisp_State *K, mp_rat r); /* Common code for addition and subtraction operations on rationals. */ -static mp_result s_rat_combine(mp_rat a, mp_rat b, mp_rat c, - mp_result (*comb_f)(mp_int, mp_int, mp_int)); +static mp_result s_rat_combine(klisp_State *K, mp_rat a, mp_rat b, mp_rat c, + mp_result (*comb_f) + (klisp_State *,mp_int, mp_int, mp_int)); /* {{{ mp_rat_init(r) */ -mp_result mp_rat_init(mp_rat r) +mp_result mp_rat_init(klisp_State *K, mp_rat r) { - return mp_rat_init_size(r, 0, 0); + return mp_rat_init_size(K, r, 0, 0); } /* }}} */ /* {{{ mp_rat_alloc() */ -mp_rat mp_rat_alloc(void) +mp_rat mp_rat_alloc(klisp_State *K) { - mp_rat out = malloc(sizeof(*out)); - - if(out != NULL) { - if(mp_rat_init(out) != MP_OK) { - free(out); - return NULL; + mp_rat out = klispM_new(K, mpq_t); + + if(out != NULL) { + if(mp_rat_init(K, out) != MP_OK) { + klispM_free(K, out); + return NULL; + } } - } - return out; + return out; } /* }}} */ /* {{{ mp_rat_init_size(r, n_prec, d_prec) */ -mp_result mp_rat_init_size(mp_rat r, mp_size n_prec, mp_size d_prec) +mp_result mp_rat_init_size(klisp_State *K, mp_rat r, mp_size n_prec, + mp_size d_prec) { - mp_result res; + mp_result res; - if((res = mp_int_init_size(MP_NUMER_P(r), n_prec)) != MP_OK) - return res; - if((res = mp_int_init_size(MP_DENOM_P(r), d_prec)) != MP_OK) { - mp_int_clear(MP_NUMER_P(r)); - return res; - } + if((res = mp_int_init_size(K, MP_NUMER_P(r), n_prec)) != MP_OK) + return res; + if((res = mp_int_init_size(K, MP_DENOM_P(r), d_prec)) != MP_OK) { + mp_int_clear(K, MP_NUMER_P(r)); + return res; + } - return mp_int_set_value(MP_DENOM_P(r), 1); + return mp_int_set_value(K, MP_DENOM_P(r), 1); } /* }}} */ /* {{{ mp_rat_init_copy(r, old) */ -mp_result mp_rat_init_copy(mp_rat r, mp_rat old) +mp_result mp_rat_init_copy(klisp_State *K, mp_rat r, mp_rat old) { - mp_result res; + mp_result res; - if((res = mp_int_init_copy(MP_NUMER_P(r), MP_NUMER_P(old))) != MP_OK) - return res; - if((res = mp_int_init_copy(MP_DENOM_P(r), MP_DENOM_P(old))) != MP_OK) - mp_int_clear(MP_NUMER_P(r)); + if((res = mp_int_init_copy(K, MP_NUMER_P(r), MP_NUMER_P(old))) != MP_OK) + return res; + if((res = mp_int_init_copy(K, MP_DENOM_P(r), MP_DENOM_P(old))) != MP_OK) + mp_int_clear(K, MP_NUMER_P(r)); - return res; + return res; } /* }}} */ /* {{{ mp_rat_set_value(r, numer, denom) */ -mp_result mp_rat_set_value(mp_rat r, int numer, int denom) +mp_result mp_rat_set_value(klisp_State *K, mp_rat r, int numer, int denom) { - mp_result res; + mp_result res; - if(denom == 0) - return MP_UNDEF; + if(denom == 0) + return MP_UNDEF; - if((res = mp_int_set_value(MP_NUMER_P(r), numer)) != MP_OK) - return res; - if((res = mp_int_set_value(MP_DENOM_P(r), denom)) != MP_OK) - return res; + if((res = mp_int_set_value(K, MP_NUMER_P(r), numer)) != MP_OK) + return res; + if((res = mp_int_set_value(K, MP_DENOM_P(r), denom)) != MP_OK) + return res; - return s_rat_reduce(r); + return s_rat_reduce(K, r); } /* }}} */ /* {{{ mp_rat_clear(r) */ -void mp_rat_clear(mp_rat r) +void mp_rat_clear(klisp_State *K, mp_rat r) { - mp_int_clear(MP_NUMER_P(r)); - mp_int_clear(MP_DENOM_P(r)); + mp_int_clear(K, MP_NUMER_P(r)); + mp_int_clear(K, MP_DENOM_P(r)); } /* }}} */ /* {{{ mp_rat_free(r) */ -void mp_rat_free(mp_rat r) +void mp_rat_free(klisp_State *K, mp_rat r) { - NRCHECK(r != NULL); + NRCHECK(r != NULL); - if(r->num.digits != NULL) - mp_rat_clear(r); + if(r->num.digits != NULL) + mp_rat_clear(K, r); - free(r); + klispM_free(K, r); } /* }}} */ /* {{{ mp_rat_numer(r, z) */ -mp_result mp_rat_numer(mp_rat r, mp_int z) +mp_result mp_rat_numer(klisp_State *K, mp_rat r, mp_int z) { - return mp_int_copy(MP_NUMER_P(r), z); + return mp_int_copy(K, MP_NUMER_P(r), z); } /* }}} */ /* {{{ mp_rat_denom(r, z) */ -mp_result mp_rat_denom(mp_rat r, mp_int z) +mp_result mp_rat_denom(klisp_State *K, mp_rat r, mp_int z) { - return mp_int_copy(MP_DENOM_P(r), z); + return mp_int_copy(K, MP_DENOM_P(r), z); } /* }}} */ @@ -171,99 +173,99 @@ mp_result mp_rat_denom(mp_rat r, mp_int z) mp_sign mp_rat_sign(mp_rat r) { - return MP_SIGN(MP_NUMER_P(r)); + return MP_SIGN(MP_NUMER_P(r)); } /* }}} */ /* {{{ mp_rat_copy(a, c) */ -mp_result mp_rat_copy(mp_rat a, mp_rat c) +mp_result mp_rat_copy(klisp_State *K, mp_rat a, mp_rat c) { - mp_result res; + mp_result res; - if((res = mp_int_copy(MP_NUMER_P(a), MP_NUMER_P(c))) != MP_OK) - return res; + if((res = mp_int_copy(K, MP_NUMER_P(a), MP_NUMER_P(c))) != MP_OK) + return res; - res = mp_int_copy(MP_DENOM_P(a), MP_DENOM_P(c)); - return res; + res = mp_int_copy(K, MP_DENOM_P(a), MP_DENOM_P(c)); + return res; } /* }}} */ /* {{{ mp_rat_zero(r) */ -void mp_rat_zero(mp_rat r) +void mp_rat_zero(klisp_State *K, mp_rat r) { - mp_int_zero(MP_NUMER_P(r)); - mp_int_set_value(MP_DENOM_P(r), 1); - + mp_int_zero(MP_NUMER_P(r)); + mp_int_set_value(K, MP_DENOM_P(r), 1); } /* }}} */ /* {{{ mp_rat_abs(a, c) */ -mp_result mp_rat_abs(mp_rat a, mp_rat c) +mp_result mp_rat_abs(klisp_State *K, mp_rat a, mp_rat c) { - mp_result res; + mp_result res; - if((res = mp_int_abs(MP_NUMER_P(a), MP_NUMER_P(c))) != MP_OK) - return res; + if((res = mp_int_abs(K, MP_NUMER_P(a), MP_NUMER_P(c))) != MP_OK) + return res; - res = mp_int_abs(MP_DENOM_P(a), MP_DENOM_P(c)); - return res; + res = mp_int_abs(K, MP_DENOM_P(a), MP_DENOM_P(c)); + return res; } /* }}} */ /* {{{ mp_rat_neg(a, c) */ -mp_result mp_rat_neg(mp_rat a, mp_rat c) +mp_result mp_rat_neg(klisp_State *K, mp_rat a, mp_rat c) { - mp_result res; + mp_result res; - if((res = mp_int_neg(MP_NUMER_P(a), MP_NUMER_P(c))) != MP_OK) - return res; + if((res = mp_int_neg(K, MP_NUMER_P(a), + MP_NUMER_P(c))) != MP_OK) + return res; - res = mp_int_copy(MP_DENOM_P(a), MP_DENOM_P(c)); - return res; + res = mp_int_copy(K, MP_DENOM_P(a), MP_DENOM_P(c)); + return res; } /* }}} */ /* {{{ mp_rat_recip(a, c) */ -mp_result mp_rat_recip(mp_rat a, mp_rat c) +mp_result mp_rat_recip(klisp_State *K, mp_rat a, mp_rat c) { - mp_result res; + mp_result res; - if(mp_rat_compare_zero(a) == 0) - return MP_UNDEF; + if(mp_rat_compare_zero(a) == 0) + return MP_UNDEF; - if((res = mp_rat_copy(a, c)) != MP_OK) - return res; + if((res = mp_rat_copy(K, a, c)) != MP_OK) + return res; - mp_int_swap(MP_NUMER_P(c), MP_DENOM_P(c)); + mp_int_swap(MP_NUMER_P(c), MP_DENOM_P(c)); - /* Restore the signs of the swapped elements */ - { - mp_sign tmp = MP_SIGN(MP_NUMER_P(c)); + /* Restore the signs of the swapped elements */ + { + mp_sign tmp = MP_SIGN(MP_NUMER_P(c)); - MP_SIGN(MP_NUMER_P(c)) = MP_SIGN(MP_DENOM_P(c)); - MP_SIGN(MP_DENOM_P(c)) = tmp; - } + MP_SIGN(MP_NUMER_P(c)) = MP_SIGN(MP_DENOM_P(c)); + MP_SIGN(MP_DENOM_P(c)) = tmp; + } - return MP_OK; + return MP_OK; } /* }}} */ /* {{{ mp_rat_add(a, b, c) */ -mp_result mp_rat_add(mp_rat a, mp_rat b, mp_rat c) +mp_result mp_rat_add(klisp_State *K, mp_rat a, mp_rat b, mp_rat c) { - return s_rat_combine(a, b, c, mp_int_add); + return s_rat_combine(K, a, b, c, mp_int_add); } @@ -271,9 +273,9 @@ mp_result mp_rat_add(mp_rat a, mp_rat b, mp_rat c) /* {{{ mp_rat_sub(a, b, c) */ -mp_result mp_rat_sub(mp_rat a, mp_rat b, mp_rat c) +mp_result mp_rat_sub(klisp_State *K, mp_rat a, mp_rat b, mp_rat c) { - return s_rat_combine(a, b, c, mp_int_sub); + return s_rat_combine(K, a, b, c, mp_int_sub); } @@ -281,231 +283,236 @@ mp_result mp_rat_sub(mp_rat a, mp_rat b, mp_rat c) /* {{{ mp_rat_mul(a, b, c) */ -mp_result mp_rat_mul(mp_rat a, mp_rat b, mp_rat c) +mp_result mp_rat_mul(klisp_State *K, mp_rat a, mp_rat b, mp_rat c) { - mp_result res; + mp_result res; - if((res = mp_int_mul(MP_NUMER_P(a), MP_NUMER_P(b), MP_NUMER_P(c))) != MP_OK) - return res; + if((res = mp_int_mul(K, MP_NUMER_P(a), MP_NUMER_P(b), + MP_NUMER_P(c))) != MP_OK) + return res; - if(mp_int_compare_zero(MP_NUMER_P(c)) != 0) { - if((res = mp_int_mul(MP_DENOM_P(a), MP_DENOM_P(b), MP_DENOM_P(c))) != MP_OK) - return res; - } + if(mp_int_compare_zero(MP_NUMER_P(c)) != 0) { + if((res = mp_int_mul(K, MP_DENOM_P(a), MP_DENOM_P(b), + MP_DENOM_P(c))) != MP_OK) + return res; + } - return s_rat_reduce(c); + return s_rat_reduce(K, c); } /* }}} */ /* {{{ mp_int_div(a, b, c) */ -mp_result mp_rat_div(mp_rat a, mp_rat b, mp_rat c) +mp_result mp_rat_div(klisp_State *K, mp_rat a, mp_rat b, mp_rat c) { - mp_result res = MP_OK; + mp_result res = MP_OK; - if(mp_rat_compare_zero(b) == 0) - return MP_UNDEF; + if(mp_rat_compare_zero(b) == 0) + return MP_UNDEF; - if(c == a || c == b) { - mpz_t tmp; + if(c == a || c == b) { + mpz_t tmp; - if((res = mp_int_init(&tmp)) != MP_OK) return res; - if((res = mp_int_mul(MP_NUMER_P(a), MP_DENOM_P(b), &tmp)) != MP_OK) - goto CLEANUP; - if((res = mp_int_mul(MP_DENOM_P(a), MP_NUMER_P(b), MP_DENOM_P(c))) != MP_OK) - goto CLEANUP; - res = mp_int_copy(&tmp, MP_NUMER_P(c)); - - CLEANUP: - mp_int_clear(&tmp); - } - else { - if((res = mp_int_mul(MP_NUMER_P(a), MP_DENOM_P(b), MP_NUMER_P(c))) != MP_OK) - return res; - if((res = mp_int_mul(MP_DENOM_P(a), MP_NUMER_P(b), MP_DENOM_P(c))) != MP_OK) - return res; - } - - if(res != MP_OK) - return res; - else - return s_rat_reduce(c); + if((res = mp_int_init(&tmp)) != MP_OK) return res; + if((res = mp_int_mul(K, MP_NUMER_P(a), MP_DENOM_P(b), &tmp)) != MP_OK) + goto CLEANUP; + if((res = mp_int_mul(K, MP_DENOM_P(a), MP_NUMER_P(b), + MP_DENOM_P(c))) != MP_OK) + goto CLEANUP; + res = mp_int_copy(K, &tmp, MP_NUMER_P(c)); + + CLEANUP: + mp_int_clear(K, &tmp); + } + else { + if((res = mp_int_mul(K, MP_NUMER_P(a), MP_DENOM_P(b), + MP_NUMER_P(c))) != MP_OK) + return res; + if((res = mp_int_mul(K, MP_DENOM_P(a), MP_NUMER_P(b), + MP_DENOM_P(c))) != MP_OK) + return res; + } + + if(res != MP_OK) + return res; + else + return s_rat_reduce(K, c); } /* }}} */ /* {{{ mp_rat_add_int(a, b, c) */ -mp_result mp_rat_add_int(mp_rat a, mp_int b, mp_rat c) +mp_result mp_rat_add_int(klisp_State *K, mp_rat a, mp_int b, mp_rat c) { - mpz_t tmp; - mp_result res; + mpz_t tmp; + mp_result res; - if((res = mp_int_init_copy(&tmp, b)) != MP_OK) - return res; + if((res = mp_int_init_copy(K, &tmp, b)) != MP_OK) + return res; - if((res = mp_int_mul(&tmp, MP_DENOM_P(a), &tmp)) != MP_OK) - goto CLEANUP; + if((res = mp_int_mul(K, &tmp, MP_DENOM_P(a), &tmp)) != MP_OK) + goto CLEANUP; - if((res = mp_rat_copy(a, c)) != MP_OK) - goto CLEANUP; + if((res = mp_rat_copy(K, a, c)) != MP_OK) + goto CLEANUP; - if((res = mp_int_add(MP_NUMER_P(c), &tmp, MP_NUMER_P(c))) != MP_OK) - goto CLEANUP; + if((res = mp_int_add(K, MP_NUMER_P(c), &tmp, MP_NUMER_P(c))) != MP_OK) + goto CLEANUP; - res = s_rat_reduce(c); + res = s_rat_reduce(K, c); - CLEANUP: - mp_int_clear(&tmp); - return res; +CLEANUP: + mp_int_clear(K, &tmp); + return res; } /* }}} */ /* {{{ mp_rat_sub_int(a, b, c) */ -mp_result mp_rat_sub_int(mp_rat a, mp_int b, mp_rat c) +mp_result mp_rat_sub_int(klisp_State *K, mp_rat a, mp_int b, mp_rat c) { - mpz_t tmp; - mp_result res; + mpz_t tmp; + mp_result res; - if((res = mp_int_init_copy(&tmp, b)) != MP_OK) - return res; + if((res = mp_int_init_copy(K, &tmp, b)) != MP_OK) + return res; - if((res = mp_int_mul(&tmp, MP_DENOM_P(a), &tmp)) != MP_OK) - goto CLEANUP; + if((res = mp_int_mul(K, &tmp, MP_DENOM_P(a), &tmp)) != MP_OK) + goto CLEANUP; - if((res = mp_rat_copy(a, c)) != MP_OK) - goto CLEANUP; + if((res = mp_rat_copy(K, a, c)) != MP_OK) + goto CLEANUP; - if((res = mp_int_sub(MP_NUMER_P(c), &tmp, MP_NUMER_P(c))) != MP_OK) - goto CLEANUP; + if((res = mp_int_sub(K, MP_NUMER_P(c), &tmp, MP_NUMER_P(c))) != MP_OK) + goto CLEANUP; - res = s_rat_reduce(c); + res = s_rat_reduce(K, c); - CLEANUP: - mp_int_clear(&tmp); - return res; +CLEANUP: + mp_int_clear(K, &tmp); + return res; } /* }}} */ /* {{{ mp_rat_mul_int(a, b, c) */ -mp_result mp_rat_mul_int(mp_rat a, mp_int b, mp_rat c) +mp_result mp_rat_mul_int(klisp_State *K, mp_rat a, mp_int b, mp_rat c) { - mp_result res; + mp_result res; - if((res = mp_rat_copy(a, c)) != MP_OK) - return res; + if((res = mp_rat_copy(K, a, c)) != MP_OK) + return res; - if((res = mp_int_mul(MP_NUMER_P(c), b, MP_NUMER_P(c))) != MP_OK) - return res; + if((res = mp_int_mul(K, MP_NUMER_P(c), b, MP_NUMER_P(c))) != MP_OK) + return res; - return s_rat_reduce(c); + return s_rat_reduce(K, c); } /* }}} */ /* {{{ mp_rat_div_int(a, b, c) */ -mp_result mp_rat_div_int(mp_rat a, mp_int b, mp_rat c) +mp_result mp_rat_div_int(klisp_State *K, mp_rat a, mp_int b, mp_rat c) { - mp_result res; + mp_result res; - if(mp_int_compare_zero(b) == 0) - return MP_UNDEF; + if(mp_int_compare_zero(b) == 0) + return MP_UNDEF; - if((res = mp_rat_copy(a, c)) != MP_OK) - return res; + if((res = mp_rat_copy(K, a, c)) != MP_OK) + return res; - if((res = mp_int_mul(MP_DENOM_P(c), b, MP_DENOM_P(c))) != MP_OK) - return res; + if((res = mp_int_mul(K, MP_DENOM_P(c), b, MP_DENOM_P(c))) != MP_OK) + return res; - return s_rat_reduce(c); + return s_rat_reduce(K, c); } /* }}} */ /* {{{ mp_rat_expt(a, b, c) */ -mp_result mp_rat_expt(mp_rat a, mp_small b, mp_rat c) +mp_result mp_rat_expt(klisp_State *K, mp_rat a, mp_small b, mp_rat c) { - mp_result res; + mp_result res; - /* Special cases for easy powers. */ - if(b == 0) - return mp_rat_set_value(c, 1, 1); - else if(b == 1) - return mp_rat_copy(a, c); + /* Special cases for easy powers. */ + if(b == 0) + return mp_rat_set_value(K, c, 1, 1); + else if(b == 1) + return mp_rat_copy(K, a, c); - /* Since rationals are always stored in lowest terms, it is not - necessary to reduce again when raising to an integer power. */ - if((res = mp_int_expt(MP_NUMER_P(a), b, MP_NUMER_P(c))) != MP_OK) - return res; + /* Since rationals are always stored in lowest terms, it is not + necessary to reduce again when raising to an integer power. */ + if((res = mp_int_expt(K, MP_NUMER_P(a), b, MP_NUMER_P(c))) != MP_OK) + return res; - return mp_int_expt(MP_DENOM_P(a), b, MP_DENOM_P(c)); + return mp_int_expt(K, MP_DENOM_P(a), b, MP_DENOM_P(c)); } /* }}} */ /* {{{ mp_rat_compare(a, b) */ -int mp_rat_compare(mp_rat a, mp_rat b) +int mp_rat_compare(klisp_State *K, mp_rat a, mp_rat b) { - /* Quick check for opposite signs. Works because the sign of the - numerator is always definitive. */ - if(MP_SIGN(MP_NUMER_P(a)) != MP_SIGN(MP_NUMER_P(b))) { - if(MP_SIGN(MP_NUMER_P(a)) == MP_ZPOS) - return 1; - else - return -1; - } - else { - /* Compare absolute magnitudes; if both are positive, the answer - stands, otherwise it needs to be reflected about zero. */ - int cmp = mp_rat_compare_unsigned(a, b); - - if(MP_SIGN(MP_NUMER_P(a)) == MP_ZPOS) - return cmp; - else - return -cmp; - } + /* Quick check for opposite signs. Works because the sign of the + numerator is always definitive. */ + if(MP_SIGN(MP_NUMER_P(a)) != MP_SIGN(MP_NUMER_P(b))) { + if(MP_SIGN(MP_NUMER_P(a)) == MP_ZPOS) + return 1; + else + return -1; + } + else { + /* Compare absolute magnitudes; if both are positive, the answer + stands, otherwise it needs to be reflected about zero. */ + int cmp = mp_rat_compare_unsigned(K, a, b); + + if(MP_SIGN(MP_NUMER_P(a)) == MP_ZPOS) + return cmp; + else + return -cmp; + } } /* }}} */ /* {{{ mp_rat_compare_unsigned(a, b) */ -int mp_rat_compare_unsigned(mp_rat a, mp_rat b) +int mp_rat_compare_unsigned(klisp_State *K, mp_rat a, mp_rat b) { - /* If the denominators are equal, we can quickly compare numerators - without multiplying. Otherwise, we actually have to do some work. */ - if(mp_int_compare_unsigned(MP_DENOM_P(a), MP_DENOM_P(b)) == 0) - return mp_int_compare_unsigned(MP_NUMER_P(a), MP_NUMER_P(b)); - - else { - mpz_t temp[2]; - mp_result res; - int cmp = INT_MAX, last = 0; - - /* t0 = num(a) * den(b), t1 = num(b) * den(a) */ - SETUP(mp_int_init_copy(TEMP(last), MP_NUMER_P(a)), last); - SETUP(mp_int_init_copy(TEMP(last), MP_NUMER_P(b)), last); - - if((res = mp_int_mul(TEMP(0), MP_DENOM_P(b), TEMP(0))) != MP_OK || - (res = mp_int_mul(TEMP(1), MP_DENOM_P(a), TEMP(1))) != MP_OK) - goto CLEANUP; + /* If the denominators are equal, we can quickly compare numerators + without multiplying. Otherwise, we actually have to do some work. */ + if(mp_int_compare_unsigned(MP_DENOM_P(a), MP_DENOM_P(b)) == 0) + return mp_int_compare_unsigned(MP_NUMER_P(a), MP_NUMER_P(b)); + + else { + mpz_t temp[2]; + mp_result res; + int cmp = INT_MAX, last = 0; + + /* t0 = num(a) * den(b), t1 = num(b) * den(a) */ + SETUP(mp_int_init_copy(K, TEMP(last), MP_NUMER_P(a)), last); + SETUP(mp_int_init_copy(K, TEMP(last), MP_NUMER_P(b)), last); + + if((res = mp_int_mul(K, TEMP(0), MP_DENOM_P(b), TEMP(0))) != MP_OK || + (res = mp_int_mul(K, TEMP(1), MP_DENOM_P(a), TEMP(1))) != MP_OK) + goto CLEANUP; - cmp = mp_int_compare_unsigned(TEMP(0), TEMP(1)); + cmp = mp_int_compare_unsigned(TEMP(0), TEMP(1)); - CLEANUP: - while(--last >= 0) - mp_int_clear(TEMP(last)); + CLEANUP: + while(--last >= 0) + mp_int_clear(K, TEMP(last)); - return cmp; - } + return cmp; + } } /* }}} */ @@ -514,7 +521,7 @@ int mp_rat_compare_unsigned(mp_rat a, mp_rat b) int mp_rat_compare_zero(mp_rat r) { - return mp_int_compare_zero(MP_NUMER_P(r)); + return mp_int_compare_zero(MP_NUMER_P(r)); } @@ -522,22 +529,22 @@ int mp_rat_compare_zero(mp_rat r) /* {{{ mp_rat_compare_value(r, n, d) */ -int mp_rat_compare_value(mp_rat r, mp_small n, mp_small d) +int mp_rat_compare_value(klisp_State *K, mp_rat r, mp_small n, mp_small d) { - mpq_t tmp; - mp_result res; - int out = INT_MAX; + mpq_t tmp; + mp_result res; + int out = INT_MAX; - if((res = mp_rat_init(&tmp)) != MP_OK) - return out; - if((res = mp_rat_set_value(&tmp, n, d)) != MP_OK) - goto CLEANUP; + if((res = mp_rat_init(K, &tmp)) != MP_OK) + return out; + if((res = mp_rat_set_value(K, &tmp, n, d)) != MP_OK) + goto CLEANUP; - out = mp_rat_compare(r, &tmp); + out = mp_rat_compare(K, r, &tmp); - CLEANUP: - mp_rat_clear(&tmp); - return out; +CLEANUP: + mp_rat_clear(K, &tmp); + return out; } /* }}} */ @@ -546,7 +553,7 @@ int mp_rat_compare_value(mp_rat r, mp_small n, mp_small d) int mp_rat_is_integer(mp_rat r) { - return (mp_int_compare_value(MP_DENOM_P(r), 1) == 0); + return (mp_int_compare_value(MP_DENOM_P(r), 1) == 0); } /* }}} */ @@ -555,174 +562,179 @@ int mp_rat_is_integer(mp_rat r) mp_result mp_rat_to_ints(mp_rat r, mp_small *num, mp_small *den) { - mp_result res; + mp_result res; - if((res = mp_int_to_int(MP_NUMER_P(r), num)) != MP_OK) - return res; + if((res = mp_int_to_int(MP_NUMER_P(r), num)) != MP_OK) + return res; - res = mp_int_to_int(MP_DENOM_P(r), den); - return res; + res = mp_int_to_int(MP_DENOM_P(r), den); + return res; } /* }}} */ /* {{{ mp_rat_to_string(r, radix, *str, limit) */ -mp_result mp_rat_to_string(mp_rat r, mp_size radix, char *str, int limit) +mp_result mp_rat_to_string(klisp_State *K, mp_rat r, mp_size radix, char *str, + int limit) { - char *start; - int len; - mp_result res; + char *start; + int len; + mp_result res; - /* Write the numerator. The sign of the rational number is written - by the underlying integer implementation. */ - if((res = mp_int_to_string(MP_NUMER_P(r), radix, str, limit)) != MP_OK) - return res; + /* Write the numerator. The sign of the rational number is written + by the underlying integer implementation. */ + if((res = mp_int_to_string(K, MP_NUMER_P(r), radix, str, limit)) != MP_OK) + return res; - /* If the value is zero, don't bother writing any denominator */ - if(mp_int_compare_zero(MP_NUMER_P(r)) == 0) - return MP_OK; + /* If the value is zero, don't bother writing any denominator */ + if(mp_int_compare_zero(MP_NUMER_P(r)) == 0) + return MP_OK; - /* Locate the end of the numerator, and make sure we are not going to - exceed the limit by writing a slash. */ - len = strlen(str); - start = str + len; - limit -= len; - if(limit == 0) - return MP_TRUNC; - - *start++ = '/'; - limit -= 1; + /* Locate the end of the numerator, and make sure we are not going to + exceed the limit by writing a slash. */ + len = strlen(str); + start = str + len; + limit -= len; + if(limit == 0) + return MP_TRUNC; + + *start++ = '/'; + limit -= 1; - res = mp_int_to_string(MP_DENOM_P(r), radix, start, limit); - return res; + res = mp_int_to_string(K, MP_DENOM_P(r), radix, start, limit); + return res; } /* }}} */ /* {{{ mp_rat_to_decimal(r, radix, prec, *str, limit) */ -mp_result mp_rat_to_decimal(mp_rat r, mp_size radix, mp_size prec, - mp_round_mode round, char *str, int limit) +mp_result mp_rat_to_decimal(klisp_State *K, mp_rat r, mp_size radix, + mp_size prec, mp_round_mode round, char *str, + int limit) { - mpz_t temp[3]; - mp_result res; - char *start = str; - int len, lead_0, left = limit, last = 0; + mpz_t temp[3]; + mp_result res; + char *start = str; + int len, lead_0, left = limit, last = 0; - SETUP(mp_int_init_copy(TEMP(last), MP_NUMER_P(r)), last); - SETUP(mp_int_init(TEMP(last)), last); - SETUP(mp_int_init(TEMP(last)), last); - - /* Get the unsigned integer part by dividing denominator into the - absolute value of the numerator. */ - mp_int_abs(TEMP(0), TEMP(0)); - if((res = mp_int_div(TEMP(0), MP_DENOM_P(r), TEMP(0), TEMP(1))) != MP_OK) - goto CLEANUP; - - /* Now: T0 = integer portion, unsigned; - T1 = remainder, from which fractional part is computed. */ - - /* Count up leading zeroes after the radix point. */ - for(lead_0 = 0; lead_0 < prec && mp_int_compare(TEMP(1), MP_DENOM_P(r)) < 0; - ++lead_0) { - if((res = mp_int_mul_value(TEMP(1), radix, TEMP(1))) != MP_OK) - goto CLEANUP; - } - - /* Multiply remainder by a power of the radix sufficient to get the - right number of significant figures. */ - if(prec > lead_0) { - if((res = mp_int_expt_value(radix, prec - lead_0, TEMP(2))) != MP_OK) - goto CLEANUP; - if((res = mp_int_mul(TEMP(1), TEMP(2), TEMP(1))) != MP_OK) - goto CLEANUP; - } - if((res = mp_int_div(TEMP(1), MP_DENOM_P(r), TEMP(1), TEMP(2))) != MP_OK) - goto CLEANUP; - - /* Now: T1 = significant digits of fractional part; - T2 = leftovers, to use for rounding. - - At this point, what we do depends on the rounding mode. The - default is MP_ROUND_DOWN, for which everything is as it should be - already. - */ - switch(round) { - int cmp; - - case MP_ROUND_UP: - if(mp_int_compare_zero(TEMP(2)) != 0) { - if(prec == 0) - res = mp_int_add_value(TEMP(0), 1, TEMP(0)); - else - res = mp_int_add_value(TEMP(1), 1, TEMP(1)); + SETUP(mp_int_init_copy(K, TEMP(last), MP_NUMER_P(r)), last); + SETUP(mp_int_init(TEMP(last)), last); + SETUP(mp_int_init(TEMP(last)), last); + + /* Get the unsigned integer part by dividing denominator into the + absolute value of the numerator. */ + mp_int_abs(K, TEMP(0), TEMP(0)); + if((res = mp_int_div(K, TEMP(0), MP_DENOM_P(r), TEMP(0), + TEMP(1))) != MP_OK) + goto CLEANUP; + + /* Now: T0 = integer portion, unsigned; + T1 = remainder, from which fractional part is computed. */ + + /* Count up leading zeroes after the radix point. */ + for(lead_0 = 0; lead_0 < prec && mp_int_compare(TEMP(1), MP_DENOM_P(r)) < 0; + ++lead_0) { + if((res = mp_int_mul_value(K, TEMP(1), radix, TEMP(1))) != MP_OK) + goto CLEANUP; } - break; - case MP_ROUND_HALF_UP: - case MP_ROUND_HALF_DOWN: - if((res = mp_int_mul_pow2(TEMP(2), 1, TEMP(2))) != MP_OK) - goto CLEANUP; + /* Multiply remainder by a power of the radix sufficient to get the + right number of significant figures. */ + if(prec > lead_0) { + if((res = mp_int_expt_value(K, radix, prec - lead_0, + TEMP(2))) != MP_OK) + goto CLEANUP; + if((res = mp_int_mul(K, TEMP(1), TEMP(2), TEMP(1))) != MP_OK) + goto CLEANUP; + } + if((res = mp_int_div(K, TEMP(1), MP_DENOM_P(r), TEMP(1), + TEMP(2))) != MP_OK) + goto CLEANUP; - cmp = mp_int_compare(TEMP(2), MP_DENOM_P(r)); + /* Now: T1 = significant digits of fractional part; + T2 = leftovers, to use for rounding. + + At this point, what we do depends on the rounding mode. The + default is MP_ROUND_DOWN, for which everything is as it should be + already. + */ + switch(round) { + int cmp; + + case MP_ROUND_UP: + if(mp_int_compare_zero(TEMP(2)) != 0) { + if(prec == 0) + res = mp_int_add_value(K, TEMP(0), 1, TEMP(0)); + else + res = mp_int_add_value(K, TEMP(1), 1, TEMP(1)); + } + break; + + case MP_ROUND_HALF_UP: + case MP_ROUND_HALF_DOWN: + if((res = mp_int_mul_pow2(K, TEMP(2), 1, TEMP(2))) != MP_OK) + goto CLEANUP; + + cmp = mp_int_compare(TEMP(2), MP_DENOM_P(r)); + + if(round == MP_ROUND_HALF_UP) + cmp += 1; + + if(cmp > 0) { + if(prec == 0) + res = mp_int_add_value(K, TEMP(0), 1, TEMP(0)); + else + res = mp_int_add_value(K, TEMP(1), 1, TEMP(1)); + } + break; + + case MP_ROUND_DOWN: + break; /* No action required */ - if(round == MP_ROUND_HALF_UP) - cmp += 1; + default: + return MP_BADARG; /* Invalid rounding specifier */ + } - if(cmp > 0) { - if(prec == 0) - res = mp_int_add_value(TEMP(0), 1, TEMP(0)); - else - res = mp_int_add_value(TEMP(1), 1, TEMP(1)); + /* The sign of the output should be the sign of the numerator, but + if all the displayed digits will be zero due to the precision, a + negative shouldn't be shown. */ + if(MP_SIGN(MP_NUMER_P(r)) == MP_NEG && + (mp_int_compare_zero(TEMP(0)) != 0 || + mp_int_compare_zero(TEMP(1)) != 0)) { + *start++ = '-'; + left -= 1; } - break; - - case MP_ROUND_DOWN: - break; /* No action required */ - - default: - return MP_BADARG; /* Invalid rounding specifier */ - } - - /* The sign of the output should be the sign of the numerator, but - if all the displayed digits will be zero due to the precision, a - negative shouldn't be shown. */ - if(MP_SIGN(MP_NUMER_P(r)) == MP_NEG && - (mp_int_compare_zero(TEMP(0)) != 0 || - mp_int_compare_zero(TEMP(1)) != 0)) { - *start++ = '-'; - left -= 1; - } - if((res = mp_int_to_string(TEMP(0), radix, start, left)) != MP_OK) - goto CLEANUP; + if((res = mp_int_to_string(K, TEMP(0), radix, start, left)) != MP_OK) + goto CLEANUP; - len = strlen(start); - start += len; - left -= len; + len = strlen(start); + start += len; + left -= len; - if(prec == 0) - goto CLEANUP; + if(prec == 0) + goto CLEANUP; - *start++ = '.'; - left -= 1; + *start++ = '.'; + left -= 1; - if(left < prec + 1) { - res = MP_TRUNC; - goto CLEANUP; - } + if(left < prec + 1) { + res = MP_TRUNC; + goto CLEANUP; + } - memset(start, '0', lead_0 - 1); - left -= lead_0; - start += lead_0 - 1; + memset(start, '0', lead_0 - 1); + left -= lead_0; + start += lead_0 - 1; - res = mp_int_to_string(TEMP(1), radix, start, left); + res = mp_int_to_string(K, TEMP(1), radix, start, left); - CLEANUP: - while(--last >= 0) - mp_int_clear(TEMP(last)); +CLEANUP: + while(--last >= 0) + mp_int_clear(K, TEMP(last)); - return res; + return res; } /* }}} */ @@ -731,19 +743,19 @@ mp_result mp_rat_to_decimal(mp_rat r, mp_size radix, mp_size prec, mp_result mp_rat_string_len(mp_rat r, mp_size radix) { - mp_result n_len, d_len = 0; + mp_result n_len, d_len = 0; - n_len = mp_int_string_len(MP_NUMER_P(r), radix); + n_len = mp_int_string_len(MP_NUMER_P(r), radix); - if(mp_int_compare_zero(MP_NUMER_P(r)) != 0) - d_len = mp_int_string_len(MP_DENOM_P(r), radix); + if(mp_int_compare_zero(MP_NUMER_P(r)) != 0) + d_len = mp_int_string_len(MP_DENOM_P(r), radix); - /* Though simplistic, this formula is correct. Space for the sign - flag is included in n_len, and the space for the NUL that is - counted in n_len counts for the separator here. The space for - the NUL counted in d_len counts for the final terminator here. */ + /* Though simplistic, this formula is correct. Space for the sign + flag is included in n_len, and the space for the NUL that is + counted in n_len counts for the separator here. The space for + the NUL counted in d_len counts for the final terminator here. */ - return n_len + d_len; + return n_len + d_len; } @@ -753,63 +765,64 @@ mp_result mp_rat_string_len(mp_rat r, mp_size radix) mp_result mp_rat_decimal_len(mp_rat r, mp_size radix, mp_size prec) { - int z_len, f_len; + int z_len, f_len; - z_len = mp_int_string_len(MP_NUMER_P(r), radix); + z_len = mp_int_string_len(MP_NUMER_P(r), radix); - if(prec == 0) - f_len = 1; /* terminator only */ - else - f_len = 1 + prec + 1; /* decimal point, digits, terminator */ + if(prec == 0) + f_len = 1; /* terminator only */ + else + f_len = 1 + prec + 1; /* decimal point, digits, terminator */ - return z_len + f_len; + return z_len + f_len; } /* }}} */ /* {{{ mp_rat_read_string(r, radix, *str) */ -mp_result mp_rat_read_string(mp_rat r, mp_size radix, const char *str) +mp_result mp_rat_read_string(klisp_State *K, mp_rat r, mp_size radix, + const char *str) { - return mp_rat_read_cstring(r, radix, str, NULL); + return mp_rat_read_cstring(K, r, radix, str, NULL); } /* }}} */ /* {{{ mp_rat_read_cstring(r, radix, *str, **end) */ -mp_result mp_rat_read_cstring(mp_rat r, mp_size radix, const char *str, - char **end) +mp_result mp_rat_read_cstring(klisp_State *K, mp_rat r, mp_size radix, + const char *str, char **end) { - mp_result res; - char *endp; + mp_result res; + char *endp; - if((res = mp_int_read_cstring(MP_NUMER_P(r), radix, str, &endp)) != MP_OK && - (res != MP_TRUNC)) - return res; + if((res = mp_int_read_cstring(K, MP_NUMER_P(r), radix, str, + &endp)) != MP_OK && (res != MP_TRUNC)) + return res; - /* Skip whitespace between numerator and (possible) separator */ - while(isspace((unsigned char) *endp)) - ++endp; + /* Skip whitespace between numerator and (possible) separator */ + while(isspace((unsigned char) *endp)) + ++endp; - /* If there is no separator, we will stop reading at this point. */ - if(*endp != '/') { - mp_int_set_value(MP_DENOM_P(r), 1); - if(end != NULL) - *end = endp; - return res; - } + /* If there is no separator, we will stop reading at this point. */ + if(*endp != '/') { + mp_int_set_value(K, MP_DENOM_P(r), 1); + if(end != NULL) + *end = endp; + return res; + } - ++endp; /* skip separator */ - if((res = mp_int_read_cstring(MP_DENOM_P(r), radix, endp, end)) != MP_OK) - return res; + ++endp; /* skip separator */ + if((res = mp_int_read_cstring(K, MP_DENOM_P(r), radix, endp, end)) != MP_OK) + return res; - /* Make sure the value is well-defined */ - if(mp_int_compare_zero(MP_DENOM_P(r)) == 0) - return MP_UNDEF; + /* Make sure the value is well-defined */ + if(mp_int_compare_zero(MP_DENOM_P(r)) == 0) + return MP_UNDEF; - /* Reduce to lowest terms */ - return s_rat_reduce(r); + /* Reduce to lowest terms */ + return s_rat_reduce(K, r); } /* }}} */ @@ -820,169 +833,174 @@ mp_result mp_rat_read_cstring(mp_rat r, mp_size radix, const char *str, supplied as zero to use "default" behaviour. This function will accept either a/b notation or decimal notation. - */ -mp_result mp_rat_read_ustring(mp_rat r, mp_size radix, const char *str, - char **end) +*/ +mp_result mp_rat_read_ustring(klisp_State *K, mp_rat r, mp_size radix, + const char *str, char **end) { - char *endp; - mp_result res; - - if(radix == 0) - radix = 10; /* default to decimal input */ - - if((res = mp_rat_read_cstring(r, radix, str, &endp)) != MP_OK) { - if(res == MP_TRUNC) { - if(*endp == '.') - res = mp_rat_read_cdecimal(r, radix, str, &endp); + char *endp; + mp_result res; + + if(radix == 0) + radix = 10; /* default to decimal input */ + + if((res = mp_rat_read_cstring(K, r, radix, str, &endp)) != MP_OK) { + if(res == MP_TRUNC) { + if(*endp == '.') + res = mp_rat_read_cdecimal(K, r, radix, str, &endp); + } + else + return res; } - else - return res; - } - if(end != NULL) - *end = endp; + if(end != NULL) + *end = endp; - return res; + return res; } /* }}} */ /* {{{ mp_rat_read_decimal(r, radix, *str) */ -mp_result mp_rat_read_decimal(mp_rat r, mp_size radix, const char *str) +mp_result mp_rat_read_decimal(klisp_State *K, mp_rat r, mp_size radix, + const char *str) { - return mp_rat_read_cdecimal(r, radix, str, NULL); + return mp_rat_read_cdecimal(K, r, radix, str, NULL); } /* }}} */ /* {{{ mp_rat_read_cdecimal(r, radix, *str, **end) */ -mp_result mp_rat_read_cdecimal(mp_rat r, mp_size radix, const char *str, - char **end) +mp_result mp_rat_read_cdecimal(klisp_State *K, mp_rat r, mp_size radix, + const char *str, char **end) { - mp_result res; - mp_sign osign; - char *endp; + mp_result res; + mp_sign osign; + char *endp; - while(isspace((unsigned char) *str)) - ++str; + while(isspace((unsigned char) *str)) + ++str; - switch(*str) { - case '-': - osign = MP_NEG; - break; - default: - osign = MP_ZPOS; - } + switch(*str) { + case '-': + osign = MP_NEG; + break; + default: + osign = MP_ZPOS; + } - if((res = mp_int_read_cstring(MP_NUMER_P(r), radix, str, &endp)) != MP_OK && - (res != MP_TRUNC)) - return res; + if((res = mp_int_read_cstring(K, MP_NUMER_P(r), radix, str, + &endp)) != MP_OK && (res != MP_TRUNC)) + return res; - /* This needs to be here. */ - (void) mp_int_set_value(MP_DENOM_P(r), 1); + /* This needs to be here. */ + (void) mp_int_set_value(K, MP_DENOM_P(r), 1); - if(*endp != '.') { - if(end != NULL) - *end = endp; - return res; - } - - /* If the character following the decimal point is whitespace or a - sign flag, we will consider this a truncated value. This special - case is because mp_int_read_string() will consider whitespace or - sign flags to be valid starting characters for a value, and we do - not want them following the decimal point. - - Once we have done this check, it is safe to read in the value of - the fractional piece as a regular old integer. - */ - ++endp; - if(*endp == '\0') { - if(end != NULL) - *end = endp; - return MP_OK; - } - else if(isspace((unsigned char) *endp) || *endp == '-' || *endp == '+') { - return MP_TRUNC; - } - else { - mpz_t frac; - mp_result save_res; - char *save = endp; - int num_lz = 0; - - /* Make a temporary to hold the part after the decimal point. */ - if((res = mp_int_init(&frac)) != MP_OK) - return res; + if(*endp != '.') { + if(end != NULL) + *end = endp; + return res; + } + + /* If the character following the decimal point is whitespace or a + sign flag, we will consider this a truncated value. This special + case is because mp_int_read_string() will consider whitespace or + sign flags to be valid starting characters for a value, and we do + not want them following the decimal point. + + Once we have done this check, it is safe to read in the value of + the fractional piece as a regular old integer. + */ + ++endp; + if(*endp == '\0') { + if(end != NULL) + *end = endp; + return MP_OK; + } + else if(isspace((unsigned char) *endp) || *endp == '-' || *endp == '+') { + return MP_TRUNC; + } + else { + mpz_t frac; + mp_result save_res; + char *save = endp; + int num_lz = 0; + + /* Make a temporary to hold the part after the decimal point. */ + if((res = mp_int_init(&frac)) != MP_OK) + return res; - if((res = mp_int_read_cstring(&frac, radix, endp, &endp)) != MP_OK && - (res != MP_TRUNC)) - goto CLEANUP; + if((res = mp_int_read_cstring(K, &frac, radix, endp, &endp)) != MP_OK && + (res != MP_TRUNC)) + goto CLEANUP; - /* Save this response for later. */ - save_res = res; + /* Save this response for later. */ + save_res = res; - if(mp_int_compare_zero(&frac) == 0) - goto FINISHED; + if(mp_int_compare_zero(&frac) == 0) + goto FINISHED; - /* Discard trailing zeroes (somewhat inefficiently) */ - while(mp_int_divisible_value(&frac, radix)) - if((res = mp_int_div_value(&frac, radix, &frac, NULL)) != MP_OK) - goto CLEANUP; + /* Discard trailing zeroes (somewhat inefficiently) */ + while(mp_int_divisible_value(K, &frac, radix)) + if((res = mp_int_div_value(K, &frac, radix, &frac, NULL)) != MP_OK) + goto CLEANUP; - /* Count leading zeros after the decimal point */ - while(save[num_lz] == '0') - ++num_lz; - - /* Find the least power of the radix that is at least as large as - the significant value of the fractional part, ignoring leading - zeroes. */ - (void) mp_int_set_value(MP_DENOM_P(r), radix); + /* Count leading zeros after the decimal point */ + while(save[num_lz] == '0') + ++num_lz; + + /* Find the least power of the radix that is at least as large as + the significant value of the fractional part, ignoring leading + zeroes. */ + (void) mp_int_set_value(K, MP_DENOM_P(r), radix); - while(mp_int_compare(MP_DENOM_P(r), &frac) < 0) { - if((res = mp_int_mul_value(MP_DENOM_P(r), radix, MP_DENOM_P(r))) != MP_OK) - goto CLEANUP; - } + while(mp_int_compare(MP_DENOM_P(r), &frac) < 0) { + if((res = mp_int_mul_value(K, MP_DENOM_P(r), radix, + MP_DENOM_P(r))) != MP_OK) + goto CLEANUP; + } - /* Also shift by enough to account for leading zeroes */ - while(num_lz > 0) { - if((res = mp_int_mul_value(MP_DENOM_P(r), radix, MP_DENOM_P(r))) != MP_OK) - goto CLEANUP; - - --num_lz; - } - - /* Having found this power, shift the numerator leftward that - many, digits, and add the nonzero significant digits of the - fractional part to get the result. */ - if((res = mp_int_mul(MP_NUMER_P(r), MP_DENOM_P(r), MP_NUMER_P(r))) != MP_OK) - goto CLEANUP; + /* Also shift by enough to account for leading zeroes */ + while(num_lz > 0) { + if((res = mp_int_mul_value(K, MP_DENOM_P(r), radix, + MP_DENOM_P(r))) != MP_OK) + goto CLEANUP; + + --num_lz; + } + + /* Having found this power, shift the numerator leftward that + many, digits, and add the nonzero significant digits of the + fractional part to get the result. */ + if((res = mp_int_mul(K, MP_NUMER_P(r), MP_DENOM_P(r), + MP_NUMER_P(r))) != MP_OK) + goto CLEANUP; - { /* This addition needs to be unsigned. */ - MP_SIGN(MP_NUMER_P(r)) = MP_ZPOS; - if((res = mp_int_add(MP_NUMER_P(r), &frac, MP_NUMER_P(r))) != MP_OK) - goto CLEANUP; - - MP_SIGN(MP_NUMER_P(r)) = osign; + { /* This addition needs to be unsigned. */ + MP_SIGN(MP_NUMER_P(r)) = MP_ZPOS; + if((res = mp_int_add(K, MP_NUMER_P(r), &frac, + MP_NUMER_P(r))) != MP_OK) + goto CLEANUP; + + MP_SIGN(MP_NUMER_P(r)) = osign; + } + if((res = s_rat_reduce(K, r)) != MP_OK) + goto CLEANUP; + + /* At this point, what we return depends on whether reading the + fractional part was truncated or not. That information is + saved from when we called mp_int_read_string() above. */ + FINISHED: + res = save_res; + if(end != NULL) + *end = endp; + + CLEANUP: + mp_int_clear(K, &frac); + + return res; } - if((res = s_rat_reduce(r)) != MP_OK) - goto CLEANUP; - - /* At this point, what we return depends on whether reading the - fractional part was truncated or not. That information is - saved from when we called mp_int_read_string() above. */ - FINISHED: - res = save_res; - if(end != NULL) - *end = endp; - - CLEANUP: - mp_int_clear(&frac); - - return res; - } } /* }}} */ @@ -992,88 +1010,92 @@ mp_result mp_rat_read_cdecimal(mp_rat r, mp_size radix, const char *str, /* {{{ s_rat_reduce(r) */ -static mp_result s_rat_reduce(mp_rat r) +static mp_result s_rat_reduce(klisp_State *K, mp_rat r) { - mpz_t gcd; - mp_result res = MP_OK; + mpz_t gcd; + mp_result res = MP_OK; - if(mp_int_compare_zero(MP_NUMER_P(r)) == 0) { - mp_int_set_value(MP_DENOM_P(r), 1); - return MP_OK; - } + if(mp_int_compare_zero(MP_NUMER_P(r)) == 0) { + mp_int_set_value(K, MP_DENOM_P(r), 1); + return MP_OK; + } - /* If the greatest common divisor of the numerator and denominator - is greater than 1, divide it out. */ - if((res = mp_int_init(&gcd)) != MP_OK) - return res; + /* If the greatest common divisor of the numerator and denominator + is greater than 1, divide it out. */ + if((res = mp_int_init(&gcd)) != MP_OK) + return res; - if((res = mp_int_gcd(MP_NUMER_P(r), MP_DENOM_P(r), &gcd)) != MP_OK) - goto CLEANUP; + if((res = mp_int_gcd(K, MP_NUMER_P(r), MP_DENOM_P(r), &gcd)) != MP_OK) + goto CLEANUP; - if(mp_int_compare_value(&gcd, 1) != 0) { - if((res = mp_int_div(MP_NUMER_P(r), &gcd, MP_NUMER_P(r), NULL)) != MP_OK) - goto CLEANUP; - if((res = mp_int_div(MP_DENOM_P(r), &gcd, MP_DENOM_P(r), NULL)) != MP_OK) - goto CLEANUP; - } + if(mp_int_compare_value(&gcd, 1) != 0) { + if((res = mp_int_div(K, MP_NUMER_P(r), &gcd, MP_NUMER_P(r), + NULL)) != MP_OK) + goto CLEANUP; + if((res = mp_int_div(K, MP_DENOM_P(r), &gcd, MP_DENOM_P(r), + NULL)) != MP_OK) + goto CLEANUP; + } - /* Fix up the signs of numerator and denominator */ - if(MP_SIGN(MP_NUMER_P(r)) == MP_SIGN(MP_DENOM_P(r))) - MP_SIGN(MP_NUMER_P(r)) = MP_SIGN(MP_DENOM_P(r)) = MP_ZPOS; - else { - MP_SIGN(MP_NUMER_P(r)) = MP_NEG; - MP_SIGN(MP_DENOM_P(r)) = MP_ZPOS; - } + /* Fix up the signs of numerator and denominator */ + if(MP_SIGN(MP_NUMER_P(r)) == MP_SIGN(MP_DENOM_P(r))) + MP_SIGN(MP_NUMER_P(r)) = MP_SIGN(MP_DENOM_P(r)) = MP_ZPOS; + else { + MP_SIGN(MP_NUMER_P(r)) = MP_NEG; + MP_SIGN(MP_DENOM_P(r)) = MP_ZPOS; + } - CLEANUP: - mp_int_clear(&gcd); +CLEANUP: + mp_int_clear(K, &gcd); - return res; + return res; } /* }}} */ /* {{{ s_rat_combine(a, b, c, comb_f) */ -static mp_result s_rat_combine(mp_rat a, mp_rat b, mp_rat c, - mp_result (*comb_f)(mp_int, mp_int, mp_int)) +static mp_result s_rat_combine(klisp_State *K, mp_rat a, mp_rat b, mp_rat c, + mp_result (*comb_f)(klisp_State *K, mp_int, + mp_int, mp_int)) { - mp_result res; - - /* Shortcut when denominators are already common */ - if(mp_int_compare(MP_DENOM_P(a), MP_DENOM_P(b)) == 0) { - if((res = (comb_f)(MP_NUMER_P(a), MP_NUMER_P(b), MP_NUMER_P(c))) != MP_OK) - return res; - if((res = mp_int_copy(MP_DENOM_P(a), MP_DENOM_P(c))) != MP_OK) - return res; - - return s_rat_reduce(c); - } - else { - mpz_t temp[2]; - int last = 0; - - SETUP(mp_int_init_copy(TEMP(last), MP_NUMER_P(a)), last); - SETUP(mp_int_init_copy(TEMP(last), MP_NUMER_P(b)), last); - - if((res = mp_int_mul(TEMP(0), MP_DENOM_P(b), TEMP(0))) != MP_OK) - goto CLEANUP; - if((res = mp_int_mul(TEMP(1), MP_DENOM_P(a), TEMP(1))) != MP_OK) - goto CLEANUP; - if((res = (comb_f)(TEMP(0), TEMP(1), MP_NUMER_P(c))) != MP_OK) - goto CLEANUP; - - res = mp_int_mul(MP_DENOM_P(a), MP_DENOM_P(b), MP_DENOM_P(c)); + mp_result res; - CLEANUP: - while(--last >= 0) - mp_int_clear(TEMP(last)); + /* Shortcut when denominators are already common */ + if(mp_int_compare(MP_DENOM_P(a), MP_DENOM_P(b)) == 0) { + if((res = (comb_f)(K, MP_NUMER_P(a), MP_NUMER_P(b), + MP_NUMER_P(c))) != MP_OK) + return res; + if((res = mp_int_copy(K, MP_DENOM_P(a), MP_DENOM_P(c))) != MP_OK) + return res; + + return s_rat_reduce(K, c); + } + else { + mpz_t temp[2]; + int last = 0; - if(res == MP_OK) - return s_rat_reduce(c); - else - return res; - } + SETUP(mp_int_init_copy(K, TEMP(last), MP_NUMER_P(a)), last); + SETUP(mp_int_init_copy(K, TEMP(last), MP_NUMER_P(b)), last); + + if((res = mp_int_mul(K, TEMP(0), MP_DENOM_P(b), TEMP(0))) != MP_OK) + goto CLEANUP; + if((res = mp_int_mul(K, TEMP(1), MP_DENOM_P(a), TEMP(1))) != MP_OK) + goto CLEANUP; + if((res = (comb_f)(K, TEMP(0), TEMP(1), MP_NUMER_P(c))) != MP_OK) + goto CLEANUP; + + res = mp_int_mul(K, MP_DENOM_P(a), MP_DENOM_P(b), MP_DENOM_P(c)); + + CLEANUP: + while(--last >= 0) + mp_int_clear(K, TEMP(last)); + + if(res == MP_OK) + return s_rat_reduce(K, c); + else + return res; + } } /* }}} */ diff --git a/src/imrat.h b/src/imrat.h @@ -42,6 +42,7 @@ typedef struct mpq { #define MP_DENOM_P(Q) (&((Q)->den)) /* Pointer to denominator */ /* Rounding constants */ +/* TODO: klisp add MP_ROUND_HALF_EVEN for compatibility with floating point */ typedef enum { MP_ROUND_DOWN, MP_ROUND_HALF_UP, @@ -63,8 +64,7 @@ mp_result mp_rat_denom(klisp_State *K, mp_rat r, mp_int z); /* z = den(r) */ mp_sign mp_rat_sign(mp_rat r); mp_result mp_rat_copy(klisp_State *K, mp_rat a, mp_rat c); /* c = a */ -/* NOTE: this doesn't use the allocator */ -void mp_rat_zero(mp_rat r); /* r = 0 */ +void mp_rat_zero(klisp_State *K, mp_rat r); /* r = 0 */ mp_result mp_rat_abs(klisp_State *K, mp_rat a, mp_rat c); /* c = |a| */ mp_result mp_rat_neg(klisp_State *K, mp_rat a, mp_rat c); /* c = -a */ mp_result mp_rat_recip(klisp_State *K, mp_rat a, mp_rat c); /* c = 1 / a */ @@ -93,9 +93,11 @@ mp_result mp_rat_expt(klisp_State *K, mp_rat a, mp_small b, mp_rat c); int mp_rat_compare(klisp_State *K, mp_rat a, mp_rat b); /* a <=> b */ /* |a| <=> |b| */ int mp_rat_compare_unsigned(klisp_State *K, mp_rat a, mp_rat b); +/* NOTE: this doesn't use the allocator */ int mp_rat_compare_zero(mp_rat r); /* r <=> 0 */ int mp_rat_compare_value(klisp_State *K, mp_rat r, mp_small n, mp_small d); /* r <=> n/d */ +/* NOTE: this doesn't use the allocator */ int mp_rat_is_integer(mp_rat r); /* Convert to integers, if representable (returns MP_RANGE if not). */ @@ -104,12 +106,14 @@ mp_result mp_rat_to_ints(mp_rat r, mp_small *num, mp_small *den); /* Convert to nul-terminated string with the specified radix, writing at most limit characters including the nul terminator. */ -mp_result mp_rat_to_string(mp_rat r, mp_size radix, char *str, int limit); +mp_result mp_rat_to_string(klisp_State *K, mp_rat r, mp_size radix, char *str, + int limit); /* Convert to decimal format in the specified radix and precision, writing at most limit characters including a nul terminator. */ -mp_result mp_rat_to_decimal(mp_rat r, mp_size radix, mp_size prec, - mp_round_mode round, char *str, int limit); +mp_result mp_rat_to_decimal(klisp_State *K, mp_rat r, mp_size radix, + mp_size prec, mp_round_mode round, + char *str, int limit); /* Return the number of characters required to represent r in the given radix. May over-estimate. */ diff --git a/src/kgc.c b/src/kgc.c @@ -17,6 +17,7 @@ #include "kmem.h" #include "kport.h" #include "imath.h" +#include "imrat.h" #include "ktable.h" #include "kstring.h" @@ -90,8 +91,9 @@ static void reallymarkobject (klisp_State *K, GCObject *o) return; } #endif + case K_TBIGRAT: /* the n & d are copied in the bigrat, not pointed to */ case K_TBIGINT: - gray2black(o); /* bigint are never gray */ + gray2black(o); /* bigint & bigrats are never gray */ break; case K_TPAIR: case K_TSYMBOL: @@ -234,7 +236,8 @@ static int32_t propagatemark (klisp_State *K) { uint8_t type = o->gch.tt; switch (type) { -/* case K_TBIGINT: bigints are never gray */ +/* case K_TBIGRAT: + case K_TBIGINT: bigints & bigrats are never gray */ case K_TPAIR: { Pair *p = cast(Pair *, o); markvalue(K, p->mark); @@ -369,13 +372,17 @@ static void cleartable (GCObject *l) { } static void freeobj (klisp_State *K, GCObject *o) { - /* TODO use specific functions like in bigint & table */ + /* TODO use specific functions like in bigint, bigrat & table */ uint8_t type = o->gch.tt; switch (type) { case K_TBIGINT: { mp_int_free(K, (Bigint *)o); break; } + case K_TBIGRAT: { + mp_rat_free(K, (Bigrat *)o); + break; + } case K_TPAIR: klispM_free(K, (Pair *)o); break; diff --git a/src/kgeqp.h b/src/kgeqp.h @@ -17,6 +17,7 @@ #include "kobject.h" #include "kapplicative.h" /* for unwrap */ #include "kinteger.h" /* for kbigint_eqp */ +#include "krational.h" /* for kbigrat_eqp */ #include "klisp.h" #include "kghelpers.h" @@ -25,7 +26,6 @@ void eqp(klisp_State *K, TValue *xparams, TValue ptree, TValue denv); /* Helper (also used in equal?) */ -/* TEMP: this will change with immutable strings */ inline bool eq2p(klisp_State *K, TValue obj1, TValue obj2) { bool res = (tv_equal(obj1, obj2)); @@ -41,7 +41,12 @@ inline bool eq2p(klisp_State *K, TValue obj1, TValue obj2) that obj1 is bigint and obj is some other type and (eq? obj1 obj2) */ res = kbigint_eqp(obj1, obj2); - } + } else if (ttisbigrat(obj1)) { + /* it's important to know that it can't be the case + that obj1 is bigrat and obj is some other type and + (eq? obj1 obj2) */ + res = kbigrat_eqp(K, obj1, obj2); + } /* immutable strings are interned so are covered already */ } return res; } diff --git a/src/kghelpers.c b/src/kghelpers.c @@ -176,6 +176,63 @@ void ftyped_bpredp(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) kapply_cc(K, b2tv(res)); } +/* This is the same, but the comparison predicate takes a klisp_State */ +/* TODO unify them */ +void ftyped_kbpredp(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) +{ + (void) denv; + /* + ** xparams[0]: name symbol + ** xparams[1]: type fn pointer (as a void * in a user TValue) + ** xparams[2]: fn pointer (as a void * in a user TValue) + */ + char *name = ksymbol_buf(xparams[0]); + bool (*typep)(TValue obj) = pvalue(xparams[1]); + bool (*predp)(klisp_State *K, TValue obj1, TValue obj2) = + pvalue(xparams[2]); + + /* check the ptree is a list first to allow the structure + errors to take precedence over the type errors. */ + int32_t cpairs; + int32_t pairs = check_list(K, name, true, ptree, &cpairs); + + /* cyclical list require an extra comparison of the last + & first element of the cycle */ + int32_t comps = cpairs? pairs : pairs - 1; + + TValue tail = ptree; + bool res = true; + + /* check the type while checking the predicate. + Keep going even if the result is false to catch errors in + type */ + + if (comps == 0) { + /* this case has to be here because otherwise there is no check + for the type of the lone operand */ + TValue first = kcar(tail); + if (!(*typep)(first)) { + /* TODO show expected type */ + klispE_throw_extra(K, name, ": bad argument type"); + return; + } + } + + while(comps-- > 0) { /* comps could be -1 if ptree is () */ + TValue first = kcar(tail); + tail = kcdr(tail); /* tail only advances one place per iteration */ + TValue second = kcar(tail); + + if (!(*typep)(first) || !(*typep)(second)) { + /* TODO show expected type */ + klispE_throw_extra(K, name, ": bad argument type"); + return; + } + res &= (*predp)(K, first, second); + } + kapply_cc(K, b2tv(res)); +} + /* typed finite list. Structure error should be throw before type errors */ int32_t check_typed_list(klisp_State *K, char *name, char *typename, bool (*typep)(TValue), bool allow_infp, TValue obj, diff --git a/src/kghelpers.h b/src/kghelpers.h @@ -385,6 +385,10 @@ void ftyped_predp(klisp_State *K, TValue *xparams, TValue ptree, TValue denv); */ void ftyped_bpredp(klisp_State *K, TValue *xparams, TValue ptree, TValue denv); +/* This is the same, but the comparison predicate takes a klisp_State */ +/* TODO unify them */ +void ftyped_kbpredp(klisp_State *K, TValue *xparams, TValue ptree, TValue denv); + /* ** Continuation that ignores the value received and instead returns diff --git a/src/kgnumbers.c b/src/kgnumbers.c @@ -18,6 +18,7 @@ #include "kerror.h" #include "ksymbol.h" #include "kinteger.h" +#include "krational.h" #include "kghelpers.h" #include "kgnumbers.h" @@ -31,183 +32,226 @@ bool knumberp(TValue obj) { return ttype(obj) <= K_LAST_NUMBER_TYPE; } bool kimp_intp(TValue obj) { return ttisinteger(obj) || ttiseinf(obj); } /* obj is known to be a number */ bool kfinitep(TValue obj) { return (!ttiseinf(obj) && !ttisiinf(obj)); } -/* TEMP: for now only fixint & bigints, should also include inexact +/* TEMP: for now only fixint, bigints & rational, should also include inexact integers */ bool kintegerp(TValue obj) { return ttisinteger(obj); } - -/* 12.5.2 =? */ -/* uses typed_bpredp */ - -/* 12.5.3 <?, <=?, >?, >=? */ -/* use typed_bpredp */ - -/* Helpers for typed binary predicates */ -/* XXX: this should probably be in a file knumber.h but there is no real need for - that file yet */ - -/* this will come handy when there are more numeric types, - it is intended to be used in switch */ -/* MAYBE: change to return -1, 0, 1 to indicate which type is bigger, and - return min & max in two extra pointers passed in. Change name to - classify_types */ -inline int32_t max_ttype(TValue obj1, TValue obj2) -{ - int32_t t1 = ttype(obj1); - int32_t t2 = ttype(obj2); - - return (t1 > t2? t1 : t2); -} - -inline int32_t min_ttype(TValue obj1, TValue obj2) -{ - int32_t t1 = ttype(obj1); - int32_t t2 = ttype(obj2); - - return (t1 < t2? t1 : t2); -} - -/* TEMP: for now only fixints, bigints and exact infinities */ -bool knum_eqp(TValue n1, TValue n2) +bool krationalp(TValue obj) { return ttisrational(obj); } +/* all real are rationals in klisp */ +bool krealp(TValue obj) { - switch(max_ttype(n1, n2)) { - case K_TFIXINT: - return ivalue(n1) == ivalue(n2); - case K_TBIGINT: - if (min_ttype(n1, n2) != K_TBIGINT) { - /* NOTE: no fixint is =? to a bigint */ - return false; - } else { - /* both are bigints */ - return kbigint_eqp(n1, n2); - } - case K_TEINF: - return (tv_equal(n1, n2)); - default: - /* shouldn't happen */ - assert(0); - return false; - } -} - -bool knum_ltp(TValue n1, TValue n2) -{ - switch(max_ttype(n1, n2)) { - case K_TFIXINT: - return ivalue(n1) < ivalue(n2); - case K_TBIGINT: { - kensure_bigint(n1); - kensure_bigint(n2); - return kbigint_ltp(n1, n2); - } - case K_TEINF: - return !tv_equal(n1, n2) && (tv_equal(n1, KEMINF) || - tv_equal(n2, KEPINF)); - default: - /* shouldn't happen */ - assert(0); - return false; - } + return ttisrational(obj) || ttiseinf(obj) || ttisiinf(obj); } -bool knum_lep(TValue n1, TValue n2) { return !knum_ltp(n2, n1); } -bool knum_gtp(TValue n1, TValue n2) { return knum_ltp(n2, n1); } -bool knum_gep(TValue n1, TValue n2) { return !knum_ltp(n1, n2); } - -/* REFACTOR/MAYBE: add small inlineable plus that - first tries fixint addition and if that fails calls knum_plus */ - -/* May throw an error */ -/* GC: assumes n1 & n2 rooted */ -TValue knum_plus(klisp_State *K, TValue n1, TValue n2) -{ - switch(max_ttype(n1, n2)) { - case K_TFIXINT: { - int64_t res = (int64_t) ivalue(n1) + (int64_t) ivalue(n2); - if (res >= (int64_t) INT32_MIN && - res <= (int64_t) INT32_MAX) { - return i2tv((int32_t) res); - } /* else fall through */ - } - case K_TBIGINT: { - kensure_bigint(n1); - kensure_bigint(n2); - return kbigint_plus(K, n1, n2); - } - case K_TEINF: - if (!ttiseinf(n1)) - return n2; - else if (!ttiseinf(n2)) - return n1; - if (tv_equal(n1, n2)) - return n1; - else { - klispE_throw(K, "+: no primary value"); - return KINERT; - } - default: - klispE_throw(K, "+: unsopported type"); - return KINERT; - } -} - -/* May throw an error */ -/* GC: assumes n1 & n2 rooted */ -TValue knum_times(klisp_State *K, TValue n1, TValue n2) -{ - switch(max_ttype(n1, n2)) { - case K_TFIXINT: { - int64_t res = (int64_t) ivalue(n1) * (int64_t) ivalue(n2); - if (res >= (int64_t) INT32_MIN && - res <= (int64_t) INT32_MAX) { - return i2tv((int32_t) res); - } /* else fall through */ - } - case K_TBIGINT: { - kensure_bigint(n1); - kensure_bigint(n2); - return kbigint_times(K, n1, n2); - } - case K_TEINF: - if (!ttiseinf(n1) || !ttiseinf(n2)) { - if (kfast_zerop(n1) || kfast_zerop(n2)) { - /* report: #e+infinity * 0 has no primary value */ - klispE_throw(K, "*: result has no primary value"); - return KINERT; - } else - return knum_same_signp(n1, n2)? KEPINF : KEMINF; - } else - return (tv_equal(n1, n2))? KEPINF : KEMINF; - default: - klispE_throw(K, "*: unsopported type"); - return KINERT; - } -} - -/* May throw an error */ -/* GC: assumes n1 & n2 rooted */ -TValue knum_minus(klisp_State *K, TValue n1, TValue n2) -{ - switch(max_ttype(n1, n2)) { - case K_TFIXINT: { - int64_t res = (int64_t) ivalue(n1) - (int64_t) ivalue(n2); - if (res >= (int64_t) INT32_MIN && - res <= (int64_t) INT32_MAX) { - return i2tv((int32_t) res); - } /* else fall through */ - } - case K_TBIGINT: { - kensure_bigint(n1); - kensure_bigint(n2); - return kbigint_minus(K, n1, n2); - } - case K_TEINF: - if (!ttiseinf(n1)) - return kneg_inf(n2); - else if (!ttiseinf(n2)) - return n1; - if (tv_equal(n1, n2)) { - klispE_throw(K, "-: no primary value"); - return KINERT; + /* 12.5.2 =? */ + /* uses typed_bpredp */ + + /* 12.5.3 <?, <=?, >?, >=? */ + /* use typed_bpredp */ + + /* Helpers for typed binary predicates */ + /* XXX: this should probably be in a file knumber.h but there is no real need for + that file yet */ + + /* this will come handy when there are more numeric types, + it is intended to be used in switch */ + /* MAYBE: change to return -1, 0, 1 to indicate which type is bigger, and + return min & max in two extra pointers passed in. Change name to + classify_types */ + inline int32_t max_ttype(TValue obj1, TValue obj2) + { + int32_t t1 = ttype(obj1); + int32_t t2 = ttype(obj2); + + return (t1 > t2? t1 : t2); + } + + inline int32_t min_ttype(TValue obj1, TValue obj2) + { + int32_t t1 = ttype(obj1); + int32_t t2 = ttype(obj2); + + return (t1 < t2? t1 : t2); + } + + /* TEMP: for now only fixints, bigints, bigrats and exact infinities */ + bool knum_eqp(klisp_State *K, TValue n1, TValue n2) + { + switch(max_ttype(n1, n2)) { + case K_TFIXINT: + return ivalue(n1) == ivalue(n2); + case K_TBIGINT: + if (min_ttype(n1, n2) != K_TBIGINT) { + /* NOTE: no fixint is =? to a bigint */ + return false; + } else { + /* both are bigints */ + return kbigint_eqp(n1, n2); + } + case K_TBIGRAT: + if (min_ttype(n1, n2) != K_TBIGRAT) { + /* NOTE: no fixint or bigint is =? to a bigrat */ + return false; + } else { + /* both are bigints */ + return kbigrat_eqp(K, n1, n2); + } + case K_TEINF: + return (tv_equal(n1, n2)); + default: + /* shouldn't happen */ + assert(0); + return false; + } + } + + bool knum_ltp(klisp_State *K, TValue n1, TValue n2) + { + switch(max_ttype(n1, n2)) { + case K_TFIXINT: + return ivalue(n1) < ivalue(n2); + case K_TBIGINT: { + kensure_bigint(n1); + kensure_bigint(n2); + return kbigint_ltp(n1, n2); + } + case K_TBIGRAT: { + kensure_bigrat(n1); + kensure_bigrat(n2); + return kbigrat_ltp(K, n1, n2); + } + case K_TEINF: + return !tv_equal(n1, n2) && (tv_equal(n1, KEMINF) || + tv_equal(n2, KEPINF)); + default: + /* shouldn't happen */ + assert(0); + return false; + } + } + + bool knum_lep(klisp_State *K, TValue n1, TValue n2) + { + return !knum_ltp(K, n2, n1); + } + bool knum_gtp(klisp_State *K, TValue n1, TValue n2) + { + return knum_ltp(K, n2, n1); + } + bool knum_gep(klisp_State *K, TValue n1, TValue n2) + { + return !knum_ltp(K, n1, n2); + } + + /* REFACTOR/MAYBE: add small inlineable plus that + first tries fixint addition and if that fails calls knum_plus */ + + /* May throw an error */ + /* GC: assumes n1 & n2 rooted */ + TValue knum_plus(klisp_State *K, TValue n1, TValue n2) + { + switch(max_ttype(n1, n2)) { + case K_TFIXINT: { + int64_t res = (int64_t) ivalue(n1) + (int64_t) ivalue(n2); + if (res >= (int64_t) INT32_MIN && + res <= (int64_t) INT32_MAX) { + return i2tv((int32_t) res); + } /* else fall through */ + } + case K_TBIGINT: { + kensure_bigint(n1); + kensure_bigint(n2); + return kbigint_plus(K, n1, n2); + } + case K_TBIGRAT: { + kensure_bigrat(n1); + kensure_bigrat(n2); + return kbigrat_plus(K, n1, n2); + } + case K_TEINF: + if (!ttiseinf(n1)) + return n2; + else if (!ttiseinf(n2)) + return n1; + if (tv_equal(n1, n2)) + return n1; + else { + klispE_throw(K, "+: no primary value"); + return KINERT; + } + default: + klispE_throw(K, "+: unsopported type"); + return KINERT; + } + } + + /* May throw an error */ + /* GC: assumes n1 & n2 rooted */ + TValue knum_times(klisp_State *K, TValue n1, TValue n2) + { + switch(max_ttype(n1, n2)) { + case K_TFIXINT: { + int64_t res = (int64_t) ivalue(n1) * (int64_t) ivalue(n2); + if (res >= (int64_t) INT32_MIN && + res <= (int64_t) INT32_MAX) { + return i2tv((int32_t) res); + } /* else fall through */ + } + case K_TBIGINT: { + kensure_bigint(n1); + kensure_bigint(n2); + return kbigint_times(K, n1, n2); + } + case K_TBIGRAT: { + kensure_bigrat(n1); + kensure_bigrat(n2); + return kbigrat_times(K, n1, n2); + } + case K_TEINF: + if (!ttiseinf(n1) || !ttiseinf(n2)) { + if (kfast_zerop(n1) || kfast_zerop(n2)) { + /* report: #e+infinity * 0 has no primary value */ + klispE_throw(K, "*: result has no primary value"); + return KINERT; + } else + return knum_same_signp(n1, n2)? KEPINF : KEMINF; + } else + return (tv_equal(n1, n2))? KEPINF : KEMINF; + default: + klispE_throw(K, "*: unsopported type"); + return KINERT; + } + } + + /* May throw an error */ + /* GC: assumes n1 & n2 rooted */ + TValue knum_minus(klisp_State *K, TValue n1, TValue n2) + { + switch(max_ttype(n1, n2)) { + case K_TFIXINT: { + int64_t res = (int64_t) ivalue(n1) - (int64_t) ivalue(n2); + if (res >= (int64_t) INT32_MIN && + res <= (int64_t) INT32_MAX) { + return i2tv((int32_t) res); + } /* else fall through */ + } + case K_TBIGINT: { + kensure_bigint(n1); + kensure_bigint(n2); + return kbigint_minus(K, n1, n2); + } + case K_TBIGRAT: { + kensure_bigrat(n1); + kensure_bigrat(n2); + return kbigrat_minus(K, n1, n2); + } + case K_TEINF: + if (!ttiseinf(n1)) + return kneg_inf(n2); + else if (!ttiseinf(n2)) + return n1; + if (tv_equal(n1, n2)) { + klispE_throw(K, "-: no primary value"); + return KINERT; } else return n1; default: @@ -216,6 +260,48 @@ TValue knum_minus(klisp_State *K, TValue n1, TValue n2) } } + /* May throw an error */ + /* GC: assumes n1 & n2 rooted */ + TValue knum_divided(klisp_State *K, TValue n1, TValue n2) + { + /* first check the most common error, division by zero */ + if (kfast_zerop(n2)) { + klispE_throw(K, "/: division by zero (no primary value)"); + return KINERT; + } + + switch(max_ttype(n1, n2)) { + case K_TFIXINT: { + int64_t res = (int64_t) ivalue(n1) / (int64_t) ivalue(n2); + int64_t rem = (int64_t) ivalue(n1) % (int64_t) ivalue(n2); + if (rem == 0 && res >= (int64_t) INT32_MIN && + res <= (int64_t) INT32_MAX) { + return i2tv((int32_t) res); + } /* else fall through */ + } + case K_TBIGINT: /* just handle it as a rational */ + case K_TBIGRAT: { + kensure_bigrat(n1); + kensure_bigrat(n2); + return kbigrat_divided(K, n1, n2); + } + case K_TEINF: { + if (ttiseinf(n1) && ttiseinf(n2)) { + klispE_throw(K, "/: (infinity divided by infinity) " + "no primary value"); + return KINERT; + } else if (ttiseinf(n1)) { + return knum_same_signp(n1, n2)? KEPINF : KEMINF; + } else { /* ttiseinf(n2) */ + return i2tv(0); + } + } + default: + klispE_throw(K, "/: unsopported type"); + return KINERT; + } +} + /* GC: assumes n rooted */ TValue knum_abs(klisp_State *K, TValue n) { @@ -234,6 +320,10 @@ TValue knum_abs(klisp_State *K, TValue n) kensure_bigint(n); return kbigint_abs(K, n); } + case K_TBIGRAT: { + kensure_bigrat(n); + return kbigrat_abs(K, n); + } case K_TEINF: return KEPINF; default: @@ -307,6 +397,124 @@ TValue knum_lcm(klisp_State *K, TValue n1, TValue n2) } } +/* GC: assumes n is rooted */ +TValue knum_numerator(klisp_State *K, TValue n) +{ + switch(ttype(n)) { + case K_TFIXINT: + case K_TBIGINT: + return n; + case K_TBIGRAT: + return kbigrat_numerator(K, n); +/* case K_TEINF: infinities are not rational! */ + default: + klispE_throw(K, "numerator: unsopported type"); + return KINERT; + } +} + +/* GC: assumes n is rooted */ +TValue knum_denominator(klisp_State *K, TValue n) +{ + switch(ttype(n)) { + case K_TFIXINT: + case K_TBIGINT: + return i2tv(1); /* denominator of integer is always (+)1 */ + case K_TBIGRAT: + return kbigrat_denominator(K, n); +/* case K_TEINF: infinities are not rational! */ + default: + klispE_throw(K, "denominator: unsopported type"); + return KINERT; + } +} + +/* GC: assumes n is rooted */ +TValue knum_real_to_integer(klisp_State *K, TValue n, kround_mode mode) +{ + switch(ttype(n)) { + case K_TFIXINT: + case K_TBIGINT: + return n; /* integers are easy */ + case K_TBIGRAT: + return kbigrat_to_integer(K, n, mode); + case K_TEINF: + klispE_throw(K, "round: infinite value"); + return KINERT; + default: + klispE_throw(K, "round: unsopported type"); + return KINERT; + } +} + +TValue knum_simplest_rational(klisp_State *K, TValue n1, TValue n2) +{ + /* first check that case that n1 > n2 */ + if (knum_gtp(K, n1, n2)) { + klispE_throw(K, "simplest_rational: result with no primary value " + "(n1 > n2)"); + return KINERT; + } + + /* we know that n1 <= n2 */ + switch(max_ttype(n1, n2)) { + case K_TFIXINT: + case K_TBIGINT: /* for now do all with bigrat */ + case K_TBIGRAT: { + /* we know that n1 <= n2 */ + kensure_bigrat(n1); + kensure_bigrat(n2); + return kbigrat_simplest_rational(K, n1, n2); + } + case K_TEINF: + /* we know that n1 <= n2 */ + if (tv_equal(n1, n2)) { + klispE_throw(K, "simplest rational: result with no primary value"); + return KINERT; + } else if (knegativep(n1) && kpositivep(n2)) { + return i2tv(0); + } else if (knegativep(n1)) { + /* n1 -inf, n2 finite negative */ + /* ASK John: is this behaviour for infinities ok? */ + /* Also in the report example both 1/3 & 1/2 are simpler than + 2/5... */ + return knum_real_to_integer(K, n2, K_FLOOR); + } else { + /* n1 finite positive, n2 +inf */ + /* ASK John: is this behaviour for infinities ok? */ + return knum_real_to_integer(K, n1, K_CEILING); + } + default: + klispE_throw(K, "simplest rational: unsopported type"); + return KINERT; + } +} + +TValue knum_rationalize(klisp_State *K, TValue n1, TValue n2) +{ + switch(max_ttype(n1, n2)) { + case K_TFIXINT: + case K_TBIGINT: /* for now do all with bigrat */ + case K_TBIGRAT: { + /* we know that n1 <= n2 */ + kensure_bigrat(n1); + kensure_bigrat(n2); + return kbigrat_rationalize(K, n1, n2); + } + case K_TEINF: + if (kfinitep(n1) || !kfinitep(n2)) { + return i2tv(0); + } else { /* infinite n1, finite n2 */ + /* ASK John: is this behaviour for infinities ok? */ + klispE_throw(K, "rationalize: result with no primary value"); + return KINERT; + } + default: + klispE_throw(K, "rationalize: unsopported type"); + return KINERT; + } +} + /* 12.5.4 + */ void kplus(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) { @@ -413,7 +621,7 @@ void ktimes(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) /* think of cres as the product of an infinite series */ if (kfast_zerop(cres)) ; /* do nothing */ - else if (kpositivep(cres) && knum_ltp(cres, i2tv(1))) + else if (kpositivep(cres) && knum_ltp(K, cres, i2tv(1))) cres = i2tv(0); else if (kfast_onep(cres)) { if (all_one) @@ -422,7 +630,7 @@ void ktimes(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) klispE_throw(K, "*: result has no primary value"); return; } - } else if (knum_gtp(cres, i2tv(1))) { + } else if (knum_gtp(K, cres, i2tv(1))) { /* ASK JOHN: this is as per the report, but maybe we should check that all elements are positive... */ cres = KEPINF; @@ -595,8 +803,8 @@ void kdiv_mod(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) UNUSED(denv); - bind_2tp(K, name, ptree, "number", knumberp, tv_n, - "number", knumberp, tv_d); + bind_2tp(K, name, ptree, "real", krealp, tv_n, + "real", krealp, tv_d); TValue tv_div, tv_mod; @@ -634,6 +842,14 @@ void kdiv_mod(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) else tv_div = kbigint_div0_mod0(K, tv_n, tv_d, &tv_mod); break; + case K_TBIGRAT: + kensure_bigrat(tv_n); + kensure_bigrat(tv_d); + if ((flags & FDIV_ZERO) == 0) + tv_div = kbigrat_div_mod(K, tv_n, tv_d, &tv_mod); + else + tv_div = kbigrat_div0_mod0(K, tv_n, tv_d, &tv_mod); + break; case K_TEINF: if (ttiseinf(tv_n)) { klispE_throw_extra(K, name, ": non finite dividend"); @@ -696,6 +912,8 @@ bool kpositivep(TValue n) return ivalue(n) > 0; case K_TBIGINT: return kbigint_positivep(n); + case K_TBIGRAT: + return kbigrat_positivep(n); default: /* shouldn't happen */ assert(0); @@ -711,6 +929,8 @@ bool knegativep(TValue n) return ivalue(n) < 0; case K_TBIGINT: return kbigint_negativep(n); + case K_TBIGRAT: + return kbigrat_negativep(n); default: /* shouldn't happen */ assert(0); @@ -787,13 +1007,13 @@ void kmin_max(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) } TValue tail = ptree; - bool (*cmp)(TValue, TValue) = minp? knum_ltp : knum_gtp; + bool (*cmp)(klisp_State *K, TValue, TValue) = minp? knum_ltp : knum_gtp; while(pairs--) { TValue first = kcar(tail); tail = kcdr(tail); - if ((*cmp)(first, res)) + if ((*cmp)(K, first, res)) res = first; } kapply_cc(K, res); @@ -805,9 +1025,8 @@ void kgcd(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) UNUSED(xparams); UNUSED(denv); /* cycles are allowed, loop counting pairs */ - int32_t dummy; /* don't care about count of cycle pairs */ - int32_t pairs = check_typed_list(K, "gcd", "number", kimp_intp, true, - ptree, &dummy); + int32_t pairs = check_typed_list(K, "gcd", "improper integer", kimp_intp, + true, ptree, NULL); TValue res = i2tv(0); krooted_vars_push(K, &res); @@ -843,9 +1062,8 @@ void klcm(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) UNUSED(xparams); UNUSED(denv); /* cycles are allowed, loop counting pairs */ - int32_t dummy; /* don't care about count of cycle pairs */ - int32_t pairs = check_typed_list(K, "lcm", "number", kimp_intp, true, - ptree, &dummy); + int32_t pairs = check_typed_list(K, "lcm", "improper integer", kimp_intp, + true, ptree, NULL); /* report: this will cover the case of (lcm) = 1 */ TValue res = i2tv(1); @@ -863,3 +1081,163 @@ void klcm(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) kapply_cc(K, res); } + +/* TODO: remaining of rational module */ + +/* 12.8.1 rational? */ +/* uses ftypep */ + +/* 12.8.2 / */ +void kdivided(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) +{ + UNUSED(denv); + UNUSED(xparams); + /* cycles are allowed, loop counting pairs */ + int32_t cpairs; + + /* / in kernel (and unlike in scheme) requires at least 2 arguments */ + if (!ttispair(ptree) || !ttispair(kcdr(ptree))) { + klispE_throw(K, "/: at least two values are required"); + return; + } else if (!knumberp(kcar(ptree))) { + klispE_throw(K, "/: bad type on first argument (expected number)"); + return; + } + TValue first_val = kcar(ptree); + int32_t pairs = check_typed_list(K, "/", "number", knumberp, true, + kcdr(ptree), &cpairs); + int32_t apairs = pairs - cpairs; + + TValue res; + + /* first the acyclic part */ + TValue ares = i2tv(1); + TValue tail = kcdr(ptree); + + krooted_vars_push(K, &ares); + + while(apairs--) { + TValue first = kcar(tail); + tail = kcdr(tail); + ares = knum_times(K, ares, first); + } + + /* next the cyclic part */ + TValue cres = i2tv(1); + + if (cpairs == 0) { + /* speed things up if there is no cycle */ + res = ares; + krooted_vars_pop(K); + } else { + bool all_one = true; + + krooted_vars_push(K, &cres); + while(cpairs--) { + TValue first = kcar(tail); + tail = kcdr(tail); + all_one = all_one && kfast_onep(first); + cres = knum_times(K, cres, first); + } + + /* think of cres as the product of an infinite series */ + if (kfast_zerop(cres)) + ; /* do nothing */ + else if (kpositivep(cres) && knum_ltp(K, cres, i2tv(1))) + cres = i2tv(0); + else if (kfast_onep(cres)) { + if (all_one) + cres = i2tv(1); + else { + klispE_throw(K, "/: result has no primary value"); + return; + } + } else if (knum_gtp(K, cres, i2tv(1))) { + /* ASK JOHN: this is as per the report, but maybe we should check + that all elements are positive... */ + cres = KEPINF; + } else { + /* cycle result less than zero */ + klispE_throw(K, "/: result has no primary value"); + return; + } + + res = knum_times(K, ares, cres); + krooted_vars_pop(K); + krooted_vars_pop(K); + } + /* now divide first value by the product of all the elements in the list */ + krooted_tvs_push(K, res); + res = knum_divided(K, first_val, res); + krooted_tvs_pop(K); + + kapply_cc(K, res); +} + +/* 12.8.3 numerator, denominator */ +void knumerator(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) +{ + UNUSED(denv); + UNUSED(xparams); + + bind_1tp(K, "numerator", ptree, "rational", krationalp, n); + + TValue res = knum_numerator(K, n); + kapply_cc(K, res); +} + +void kdenominator(klisp_State *K, TValue *xparams, TValue ptree, TValue denv) +{ + UNUSED(denv); + UNUSED(xparams); + + bind_1tp(K, "denominator", ptree, "rational", krationalp, n); + + TValue res = knum_denominator(K, n); + kapply_cc(K, res); +} + +/* 12.8.4 floor, ceiling, truncate, round */ +void kreal_to_integer(klisp_State *K, TValue *xparams, TValue ptree, + TValue denv) +{ + /* + ** xparams[0]: symbol name + ** xparams[1]: bool: true min, false max + */ + UNUSED(denv); + char *name = ksymbol_buf(xparams[0]); + kround_mode mode = (kround_mode) ivalue(xparams[1]); + + bind_1tp(K, name, ptree, "real", krealp, n); + + TValue res = knum_real_to_integer(K, n, mode); + kapply_cc(K, res); +} + +/* 12.8.5 rationalize, simplest-rational */ +void krationalize(klisp_State *K, TValue *xparams, TValue ptree, + TValue denv) +{ + UNUSED(denv); + UNUSED(xparams); + + bind_2tp(K, "rationalize", ptree, "real", krealp, n1, + "real", krealp, n2); + + TValue res = knum_rationalize(K, n1, n2); + kapply_cc(K, res); +} + +void ksimplest_rational(klisp_State *K, TValue *xparams, TValue ptree, + TValue denv) +{ + UNUSED(denv); + UNUSED(xparams); + + bind_2tp(K, "simplest-rational", ptree, "real", krealp, n1, + "real", krealp, n2); + + TValue res = knum_simplest_rational(K, n1, n2); + kapply_cc(K, res); +} diff --git a/src/kgnumbers.h b/src/kgnumbers.h @@ -27,6 +27,8 @@ bool knumberp(TValue obj); bool kfinitep(TValue obj); bool kintegerp(TValue obj); +bool krationalp(TValue obj); +bool krealp(TValue obj); /* 12.5.2 =? */ @@ -38,11 +40,11 @@ bool kintegerp(TValue obj); /* Helpers for typed binary predicates */ /* XXX: this should probably be in a file knumber.h but there is no real need for that file yet */ -bool knum_eqp(TValue n1, TValue n2); -bool knum_ltp(TValue n1, TValue n2); -bool knum_lep(TValue n1, TValue n2); -bool knum_gtp(TValue n1, TValue n2); -bool knum_gep(TValue n1, TValue n2); +bool knum_eqp(klisp_State *K, TValue n1, TValue n2); +bool knum_ltp(klisp_State *K, TValue n1, TValue n2); +bool knum_lep(klisp_State *K, TValue n1, TValue n2); +bool knum_gtp(klisp_State *K, TValue n1, TValue n2); +bool knum_gep(klisp_State *K, TValue n1, TValue n2); /* 12.5.4 + */ /* TEMP: for now only accept two arguments */ @@ -109,6 +111,26 @@ void kmin_max(klisp_State *K, TValue *xparams, TValue ptree, TValue denv); void kgcd(klisp_State *K, TValue *xparams, TValue ptree, TValue denv); void klcm(klisp_State *K, TValue *xparams, TValue ptree, TValue denv); +/* 12.8.1 rational? */ +/* uses ftypep */ + +/* 12.8.2 / */ +void kdivided(klisp_State *K, TValue *xparams, TValue ptree, TValue denv); + +/* 12.8.3 numerator, denominator */ +void knumerator(klisp_State *K, TValue *xparams, TValue ptree, TValue denv); +void kdenominator(klisp_State *K, TValue *xparams, TValue ptree, TValue denv); + +/* 12.8.4 floor, ceiling, truncate, round */ +void kreal_to_integer(klisp_State *K, TValue *xparams, TValue ptree, + TValue denv); + +/* 12.8.5 rationalize, simplest-rational */ +void krationalize(klisp_State *K, TValue *xparams, TValue ptree, + TValue denv); + +void ksimplest_rational(klisp_State *K, TValue *xparams, TValue ptree, + TValue denv); /* REFACTOR: These should be in a knumber.h header */ diff --git a/src/kground.c b/src/kground.c @@ -666,29 +666,26 @@ void kinit_ground_env(klisp_State *K) p2tv(kintegerp)); /* 12.5.2 =? */ - add_applicative(K, ground_env, "=?", ftyped_bpredp, 3, + add_applicative(K, ground_env, "=?", ftyped_kbpredp, 3, symbol, p2tv(knumberp), p2tv(knum_eqp)); /* 12.5.3 <?, <=?, >?, >=? */ - add_applicative(K, ground_env, "<?", ftyped_bpredp, 3, - symbol, p2tv(knumberp), p2tv(knum_ltp)); - add_applicative(K, ground_env, "<=?", ftyped_bpredp, 3, - symbol, p2tv(knumberp), p2tv(knum_lep)); - add_applicative(K, ground_env, ">?", ftyped_bpredp, 3, - symbol, p2tv(knumberp), p2tv(knum_gtp)); - add_applicative(K, ground_env, ">=?", ftyped_bpredp, 3, - symbol, p2tv(knumberp), p2tv(knum_gep)); + add_applicative(K, ground_env, "<?", ftyped_kbpredp, 3, + symbol, p2tv(krealp), p2tv(knum_ltp)); + add_applicative(K, ground_env, "<=?", ftyped_kbpredp, 3, + symbol, p2tv(krealp), p2tv(knum_lep)); + add_applicative(K, ground_env, ">?", ftyped_kbpredp, 3, + symbol, p2tv(krealp), p2tv(knum_gtp)); + add_applicative(K, ground_env, ">=?", ftyped_kbpredp, 3, + symbol, p2tv(krealp), p2tv(knum_gep)); /* 12.5.4 + */ - /* TEMP: for now only accept two arguments */ add_applicative(K, ground_env, "+", kplus, 0); /* 12.5.5 * */ - /* TEMP: for now only accept two arguments */ add_applicative(K, ground_env, "*", ktimes, 0); /* 12.5.6 - */ - /* TEMP: for now only accept two arguments */ add_applicative(K, ground_env, "-", kminus, 0); /* 12.5.7 zero? */ @@ -713,9 +710,9 @@ void kinit_ground_env(klisp_State *K) /* 12.5.10 positive?, negative? */ add_applicative(K, ground_env, "positive?", ftyped_predp, 3, symbol, - p2tv(knumberp), p2tv(kpositivep)); + p2tv(krealp), p2tv(kpositivep)); add_applicative(K, ground_env, "negative?", ftyped_predp, 3, symbol, - p2tv(knumberp), p2tv(knegativep)); + p2tv(krealp), p2tv(knegativep)); /* 12.5.11 odd?, even? */ add_applicative(K, ground_env, "odd?", ftyped_predp, 3, symbol, @@ -734,6 +731,35 @@ void kinit_ground_env(klisp_State *K) add_applicative(K, ground_env, "gcd", kgcd, 0); add_applicative(K, ground_env, "lcm", klcm, 0); + /* + ** 12.8 Rational features + */ + + /* 12.8.1 rational? */ + add_applicative(K, ground_env, "rational?", ftypep, 2, symbol, + p2tv(krationalp)); + + /* 12.8.2 / */ + add_applicative(K, ground_env, "/", kdivided, 0); + + /* 12.8.3 numerator, denominator */ + add_applicative(K, ground_env, "numerator", knumerator, 0); + add_applicative(K, ground_env, "denominator", kdenominator, 0); + + /* 12.8.4 floor, ceiling, truncate, round */ + add_applicative(K, ground_env, "floor", kreal_to_integer, 2, + symbol, i2tv((int32_t) K_FLOOR)); + add_applicative(K, ground_env, "ceiling", kreal_to_integer, 2, + symbol, i2tv((int32_t) K_CEILING)); + add_applicative(K, ground_env, "truncate", kreal_to_integer, 2, + symbol, i2tv((int32_t) K_TRUNCATE)); + add_applicative(K, ground_env, "round", kreal_to_integer, 2, + symbol, i2tv((int32_t) K_ROUND_EVEN)); + + /* 12.8.5 rationalize, simplest-rational */ + add_applicative(K, ground_env, "rationalize", krationalize, 0); + add_applicative(K, ground_env, "simplest-rational", ksimplest_rational, 0); + /* ** ** 13 Strings diff --git a/src/kinteger.c b/src/kinteger.c @@ -15,24 +15,7 @@ #include "kmem.h" #include "kgc.h" -/* This tries to convert a bigint to a fixint */ -inline TValue kbigint_try_fixint(klisp_State *K, TValue n) -{ - Bigint *b = tv2bigint(n); - if (MP_USED(b) != 1) - return n; - - int64_t digit = (int64_t) *(MP_DIGITS(b)); - if (MP_SIGN(b) == MP_NEG) digit = -digit; - if (kfit_int32_t(digit)) { - /* n shouln't be reachable but the let the gc do its job */ - return i2tv((int32_t) digit); - } else { - return n; - } -} - -/* for now used only for reading */ +/* It is used for reading and for creating temps and res in all operations */ /* NOTE: is uint to allow INT32_MIN as positive argument in read */ TValue kbigint_new(klisp_State *K, bool sign, uint32_t digit) { @@ -58,50 +41,27 @@ TValue kbigint_new(klisp_State *K, bool sign, uint32_t digit) /* assumes src is rooted */ TValue kbigint_copy(klisp_State *K, TValue src) { - TValue copy = kbigint_new(K, false, 0); + TValue copy = kbigint_make_simple(K); /* arguments are in reverse order with respect to mp_int_copy */ UNUSED(mp_int_init_copy(K, tv2bigint(copy), tv2bigint(src))); return copy; } -/* This algorithm is like a fused multiply add on bignums, - unlike any other function here it modifies bigint. It is used in read - and it assumes that bigint is positive */ -/* GC: Assumes tv_bigint is rooted */ -void kbigint_add_digit(klisp_State *K, TValue tv_bigint, int32_t base, - int32_t digit) -{ - Bigint *bigint = tv2bigint(tv_bigint); - UNUSED(mp_int_mul_value(K, bigint, base, bigint)); - UNUSED(mp_int_add_value(K, bigint, digit, bigint)); -} - -/* This is used by the writer to get the digits of a number - tv_bigint must be positive */ -/* GC: Assumes tv_bigint is rooted */ -int32_t kbigint_remove_digit(klisp_State *K, TValue tv_bigint, int32_t base) -{ - UNUSED(K); - Bigint *bigint = tv2bigint(tv_bigint); - int32_t r; - UNUSED(mp_int_div_value(K, bigint, base, bigint, &r)); - return r; -} - -/* This is used by write to test if there is any digit left to print */ -bool kbigint_has_digits(klisp_State *K, TValue tv_bigint) -{ - UNUSED(K); - return (mp_int_compare_zero(tv2bigint(tv_bigint)) != 0); -} +/* +** read/write interface +*/ -/* Mutate the bigint to have the opposite sign, used in read - and write*/ -/* GC: Assumes tv_bigint is rooted */ -void kbigint_invert_sign(klisp_State *K, TValue tv_bigint) +/* this works for bigints & fixints, returns true if ok */ +bool kinteger_read(klisp_State *K, char *buf, int32_t base, TValue *out, + char **end) { - Bigint *bigint = tv2bigint(tv_bigint); - UNUSED(mp_int_neg(K, bigint, bigint)); + TValue res = kbigint_make_simple(K); + krooted_tvs_push(K, res); + bool ret_val = (mp_int_read_cstring(K, tv2bigint(res), base, + buf, end) == MP_OK); + krooted_tvs_pop(K); + *out = kbigint_try_fixint(K, res); + return ret_val; } /* this is used by write to estimate the number of chars necessary to @@ -111,6 +71,16 @@ int32_t kbigint_print_size(TValue tv_bigint, int32_t base) return mp_int_string_len(tv2bigint(tv_bigint), base); } +/* this is used by write */ +void kbigint_print_string(klisp_State *K, TValue tv_bigint, int32_t base, + char *buf, int32_t limit) +{ + mp_result res = mp_int_to_string(K, tv2bigint(tv_bigint), base, buf, + limit); + /* only possible error is truncation */ + klisp_assert(res == MP_OK); +} + /* Interface for kgnumbers */ bool kbigint_eqp(TValue tv_bigint1, TValue tv_bigint2) { @@ -147,7 +117,7 @@ bool kbigint_gep(TValue tv_bigint1, TValue tv_bigint2) */ TValue kbigint_plus(klisp_State *K, TValue n1, TValue n2) { - TValue res = kbigint_new(K, false, 0); + TValue res = kbigint_make_simple(K); krooted_tvs_push(K, res); UNUSED(mp_int_add(K, tv2bigint(n1), tv2bigint(n2), tv2bigint(res))); krooted_tvs_pop(K); @@ -156,7 +126,7 @@ TValue kbigint_plus(klisp_State *K, TValue n1, TValue n2) TValue kbigint_times(klisp_State *K, TValue n1, TValue n2) { - TValue res = kbigint_new(K, false, 0); + TValue res = kbigint_make_simple(K); krooted_tvs_push(K, res); UNUSED(mp_int_mul(K, tv2bigint(n1), tv2bigint(n2), tv2bigint(res))); krooted_tvs_pop(K); @@ -165,7 +135,7 @@ TValue kbigint_times(klisp_State *K, TValue n1, TValue n2) TValue kbigint_minus(klisp_State *K, TValue n1, TValue n2) { - TValue res = kbigint_new(K, false, 0); + TValue res = kbigint_make_simple(K); krooted_tvs_push(K, res); UNUSED(mp_int_sub(K, tv2bigint(n1), tv2bigint(n2), tv2bigint(res))); krooted_tvs_pop(K); @@ -175,9 +145,9 @@ TValue kbigint_minus(klisp_State *K, TValue n1, TValue n2) /* NOTE: n2 can't be zero, that case should be checked before calling this */ TValue kbigint_div_mod(klisp_State *K, TValue n1, TValue n2, TValue *res_r) { - TValue tv_q = kbigint_new(K, false, 0); + TValue tv_q = kbigint_make_simple(K); krooted_tvs_push(K, tv_q); - TValue tv_r = kbigint_new(K, false, 0); + TValue tv_r = kbigint_make_simple(K); krooted_tvs_push(K, tv_r); Bigint *n = tv2bigint(n1); @@ -209,9 +179,9 @@ TValue kbigint_div_mod(klisp_State *K, TValue n1, TValue n2, TValue *res_r) TValue kbigint_div0_mod0(klisp_State *K, TValue n1, TValue n2, TValue *res_r) { /* GC: root bigints */ - TValue tv_q = kbigint_new(K, false, 0); + TValue tv_q = kbigint_make_simple(K); krooted_tvs_push(K, tv_q); - TValue tv_r = kbigint_new(K, false, 0); + TValue tv_r = kbigint_make_simple(K); krooted_tvs_push(K, tv_r); Bigint *n = tv2bigint(n1); @@ -223,12 +193,12 @@ TValue kbigint_div0_mod0(klisp_State *K, TValue n1, TValue n2, TValue *res_r) /* Adjust q & r so that -|d/2| <= r < |d/2| */ /* It seems easier to check -|d| <= 2r < |d| */ - TValue tv_two_r = kbigint_new(K, false, 0); + TValue tv_two_r = kbigint_make_simple(K); krooted_tvs_push(K, tv_two_r); Bigint *two_r = tv2bigint(tv_two_r); /* two_r = r * 2 = r * 2^1 */ UNUSED(mp_int_mul_pow2(K, r, 1, two_r)); - TValue tv_abs_d = kbigint_new(K, false, 0); + TValue tv_abs_d = kbigint_make_simple(K); krooted_tvs_push(K, tv_abs_d); /* NOTE: this makes a copy if d >= 0 */ Bigint *abs_d = tv2bigint(tv_abs_d); @@ -291,7 +261,7 @@ bool kbigint_evenp(TValue tv_bigint) TValue kbigint_abs(klisp_State *K, TValue tv_bigint) { if (kbigint_negativep(tv_bigint)) { - TValue copy = kbigint_new(K, false, 0); + TValue copy = kbigint_make_simple(K); krooted_tvs_push(K, copy); UNUSED(mp_int_abs(K, tv2bigint(tv_bigint), tv2bigint(copy))); krooted_tvs_pop(K); @@ -304,7 +274,7 @@ TValue kbigint_abs(klisp_State *K, TValue tv_bigint) TValue kbigint_gcd(klisp_State *K, TValue n1, TValue n2) { - TValue res = kbigint_new(K, false, 0); + TValue res = kbigint_make_simple(K); krooted_tvs_push(K, res); UNUSED(mp_int_gcd(K, tv2bigint(n1), tv2bigint(n2), tv2bigint(res))); krooted_tvs_pop(K); @@ -313,7 +283,7 @@ TValue kbigint_gcd(klisp_State *K, TValue n1, TValue n2) TValue kbigint_lcm(klisp_State *K, TValue n1, TValue n2) { - TValue tv_res = kbigint_new(K, false, 0); + TValue tv_res = kbigint_make_simple(K); krooted_tvs_push(K, tv_res); Bigint *res = tv2bigint(tv_res); /* unlike in kernel, lcm in IMath can return a negative value diff --git a/src/kinteger.h b/src/kinteger.h @@ -15,17 +15,37 @@ #include "kstate.h" #include "imath.h" -/* for now used only for reading */ +/* Check to see if an int64_t fits in a int32_t */ +inline bool kfit_int32_t(int64_t n) { + return (n >= (int64_t) INT32_MIN && n <= (int64_t) INT32_MAX); +} + +/* This tries to convert a bigint to a fixint */ +/* XXX this doesn't need K really */ +inline TValue kbigint_try_fixint(klisp_State *K, TValue n) +{ + UNUSED(K); + Bigint *b = tv2bigint(n); + if (MP_USED(b) != 1) + return n; + + int64_t digit = (int64_t) *(MP_DIGITS(b)); + if (MP_SIGN(b) == MP_NEG) digit = -digit; + if (kfit_int32_t(digit)) { + /* n shouln't be reachable but the let the gc do its job */ + return i2tv((int32_t) digit); + } else { + return n; + } +} + /* NOTE: is uint and has flag to allow INT32_MIN as positive argument */ TValue kbigint_new(klisp_State *K, bool sign, uint32_t digit); -/* used in write to destructively get the digits */ TValue kbigint_copy(klisp_State *K, TValue src); -/* Check to see if an int64_t fits in a int32_t */ -inline bool kfit_int32_t(int64_t n) { - return (n >= (int64_t) INT32_MIN && n <= (int64_t) INT32_MAX); -} +/* macro to create the simplest bigint */ +#define kbigint_make_simple(K_) kbigint_new(K_, false, 0) /* Create a stack allocated bigints from a fixint, useful for mixed operations, relatively light weight compared @@ -42,7 +62,7 @@ inline bool kfit_int32_t(int64_t n) { (KUNIQUE_NAME(bigint)).used = 1; \ (KUNIQUE_NAME(bigint)).sign = (KUNIQUE_NAME(i)) < 0? \ MP_NEG : MP_ZPOS; \ - Bigint *name = &(KUNIQUE_NAME(bigint)); + Bigint *name = &(KUNIQUE_NAME(bigint)) /* This can be used prior to calling a bigint functions to automatically convert fixints to bigints. @@ -71,10 +91,20 @@ bool kbigint_has_digits(klisp_State *K, TValue tv_bigint); /* Mutate the bigint to have the opposite sign, used in read & write */ void kbigint_invert_sign(klisp_State *K, TValue tv_bigint); +/* read/write interface */ + +/* this works for bigints & fixints, returns true if ok */ +bool kinteger_read(klisp_State *K, char *buf, int32_t base, TValue *out, + char **end); + /* this is used by write to estimate the number of chars necessary to print the number */ int32_t kbigint_print_size(TValue tv_bigint, int32_t base); +/* this is used by write */ +void kbigint_print_string(klisp_State *K, TValue tv_bigint, int32_t base, + char *buf, int32_t limit); + /* Interface for kgnumbers */ bool kbigint_eqp(TValue bigint1, TValue bigint2); diff --git a/src/kobject.h b/src/kobject.h @@ -234,9 +234,9 @@ typedef struct __attribute__ ((__packed__)) GCheader { #define ttisinteger(o_) ({ int32_t t_ = tbasetype_(o_); \ t_ == K_TAG_FIXINT || t_ == K_TAG_BIGINT;}) #define ttisbigrat(o) (tbasetype_(o) == K_TAG_BIGRAT) -#define ttisrational(o) ({ int32_t t_ = tbasetype_(o_); \ +#define ttisrational(o_) ({ int32_t t_ = tbasetype_(o_); \ t_ == K_TAG_BIGRAT || t_== K_TAG_BIGINT || \ - t == K_TAG_FIXINT;}) + t_ == K_TAG_FIXINT;}) #define ttisnumber(o) (ttype(o) <= K_LAST_NUMBER_TYPE); }) #define ttiseinf(o) (tbasetype_(o) == K_TAG_EINF) #define ttisiinf(o) (tbasetype_(o) == K_TAG_IINF) @@ -566,6 +566,7 @@ const TValue kfree; #define gc2tv(t_, o_) ((TValue) {.tv = {.t = (t_), \ .v = { .gc = obj2gco(o_)}}}) #define gc2bigint(o_) (gc2tv(K_TAG_BIGINT, o_)) +#define gc2bigrat(o_) (gc2tv(K_TAG_BIGRAT, o_)) #define gc2pair(o_) (gc2tv(K_TAG_PAIR, o_)) #define gc2str(o_) (gc2tv(K_TAG_STRING, o_)) #define gc2sym(o_) (gc2tv(K_TAG_SYMBOL, o_)) @@ -581,6 +582,7 @@ const TValue kfree; /* Macro to convert a TValue into a specific heap allocated object */ #define tv2bigint(v_) ((Bigint *) gcvalue(v_)) +#define tv2bigrat(v_) ((Bigrat *) gcvalue(v_)) #define tv2pair(v_) ((Pair *) gcvalue(v_)) #define tv2str(v_) ((String *) gcvalue(v_)) #define tv2sym(v_) ((Symbol *) gcvalue(v_)) diff --git a/src/krational.c b/src/krational.c @@ -0,0 +1,671 @@ +/* +** krational.c +** Kernel Rationals (fixrats and bigrats) +** See Copyright Notice in klisp.h +*/ + +#include <stdbool.h> +#include <stdint.h> +#include <string.h> /* for code checking '/' & '.' */ +#include <inttypes.h> +#include <math.h> + +#include "krational.h" +#include "kinteger.h" +#include "kobject.h" +#include "kstate.h" +#include "kmem.h" +#include "kgc.h" + +/* used for res & temps in operations */ +/* NOTE: This is to be called only with already reduced values */ +TValue kbigrat_new(klisp_State *K, bool sign, uint32_t num, + uint32_t den) +{ + Bigrat *new_bigrat = klispM_new(K, Bigrat); + + /* header + gc_fields */ + klispC_link(K, (GCObject *) new_bigrat, K_TBIGRAT, 0); + + /* bigrat specific fields */ + /* If later changed to alloc obj: + GC: root bigint & put dummy value to work if garbage collections + happens while allocating array */ + new_bigrat->num.single = num; + new_bigrat->num.digits = &(new_bigrat->num.single); + new_bigrat->num.alloc = 1; + new_bigrat->num.used = 1; + new_bigrat->num.sign = sign? MP_NEG : MP_ZPOS; + + new_bigrat->den.single = den; + new_bigrat->den.digits = &(new_bigrat->den.single); + new_bigrat->den.alloc = 1; + new_bigrat->den.used = 1; + new_bigrat->den.sign = MP_ZPOS; + + return gc2bigrat(new_bigrat); +} + +/* assumes src is rooted */ +TValue kbigrat_copy(klisp_State *K, TValue src) +{ + TValue copy = kbigrat_make_simple(K); + /* arguments are in reverse order with respect to mp_rat_copy */ + UNUSED(mp_rat_init_copy(K, tv2bigrat(copy), tv2bigrat(src))); + return copy; +} + +/* +** read/write interface +*/ +/* this works for bigrats, bigints & fixints, returns true if ok */ +bool krational_read(klisp_State *K, char *buf, int32_t base, TValue *out, + char **end) +{ + TValue res = kbigrat_make_simple(K); + krooted_tvs_push(K, res); + bool ret_val = (mp_rat_read_cstring(K, tv2bigrat(res), base, + buf, end) == MP_OK); + krooted_tvs_pop(K); + *out = kbigrat_try_integer(K, res); + + /* TODO: ideally this should be incorporated in the read code */ + /* detect sign after '/', and / before numbers, those are allowed + by imrat but not in kernel */ + if (ret_val) { + char *slash = strchr(buf, '/'); + if (slash != NULL && (slash == 0 || + (*(slash+1) == '+' || *(slash+1) == '-') || + (*(slash-1) == '+' || *(slash-1) == '-'))) + ret_val = false; + } + + return ret_val; +} + +/* NOTE: allow decimal for use after #e */ +bool krational_read_decimal(klisp_State *K, char *buf, int32_t base, TValue *out, + char **end) +{ + char *my_end; + if (!end) /* always get the last char not read */ + end = &my_end; + + TValue res = kbigrat_make_simple(K); + krooted_tvs_push(K, res); + bool ret_val = (mp_rat_read_ustring(K, tv2bigrat(res), base, + buf, end) == MP_OK); + krooted_tvs_pop(K); + *out = kbigrat_try_integer(K, res); + + /* TODO: ideally this should be incorporated in the read code */ + /* detect sign after '/', or trailing '.' or starting '/' or '.'. + Those are allowed by imrat but not by kernel */ + if (ret_val) { + char *ch = strchr(buf, '/'); + if (ch != NULL && (ch == 0 || + (*(ch+1) == '+' || *(ch+1) == '-') || + (*(ch-1) == '+' || *(ch-1) == '-'))) + ret_val = false; + else { + ch = strchr(buf, '.'); + if (ch != NULL && (ch == 0 || + (*(ch+1) == '+' || *(ch+1) == '-') || + (*(ch-1) == '+' || *(ch-1) == '-') || + ch == *end - 1)) + ret_val = false; + } + } + + return ret_val; +} + +/* this is used by write to estimate the number of chars necessary to + print the number */ +int32_t kbigrat_print_size(TValue tv_bigint, int32_t base) +{ + return mp_rat_string_len(tv2bigrat(tv_bigint), base); +} + +/* this is used by write */ +void kbigrat_print_string(klisp_State *K, TValue tv_bigrat, int32_t base, + char *buf, int32_t limit) +{ + mp_result res = mp_rat_to_string(K, tv2bigrat(tv_bigrat), base, buf, + limit); + /* only possible error is truncation */ + klisp_assert(res == MP_OK); +} + +/* Interface for kgnumbers */ + +/* The compare predicates take a klisp_State because in general + may need to do multiplications */ +bool kbigrat_eqp(klisp_State *K, TValue tv_bigrat1, TValue tv_bigrat2) +{ + return (mp_rat_compare(K, tv2bigrat(tv_bigrat1), + tv2bigrat(tv_bigrat2)) == 0); +} + +bool kbigrat_ltp(klisp_State *K, TValue tv_bigrat1, TValue tv_bigrat2) +{ + return (mp_rat_compare(K, tv2bigrat(tv_bigrat1), + tv2bigrat(tv_bigrat2)) < 0); +} + +bool kbigrat_lep(klisp_State *K, TValue tv_bigrat1, TValue tv_bigrat2) +{ + return (mp_rat_compare(K, tv2bigrat(tv_bigrat1), + tv2bigrat(tv_bigrat2)) <= 0); +} + +bool kbigrat_gtp(klisp_State *K, TValue tv_bigrat1, TValue tv_bigrat2) +{ + return (mp_rat_compare(K, tv2bigrat(tv_bigrat1), + tv2bigrat(tv_bigrat2)) > 0); +} + +bool kbigrat_gep(klisp_State *K, TValue tv_bigrat1, TValue tv_bigrat2) +{ + return (mp_rat_compare(K, tv2bigrat(tv_bigrat1), + tv2bigrat(tv_bigrat2)) >= 0); +} + +/* +** GC: All of these assume the parameters are rooted +*/ +TValue kbigrat_plus(klisp_State *K, TValue n1, TValue n2) +{ + TValue res = kbigrat_make_simple(K); + krooted_tvs_push(K, res); + UNUSED(mp_rat_add(K, tv2bigrat(n1), tv2bigrat(n2), tv2bigrat(res))); + krooted_tvs_pop(K); + return kbigrat_try_integer(K, res); +} + +TValue kbigrat_times(klisp_State *K, TValue n1, TValue n2) +{ + TValue res = kbigrat_make_simple(K); + krooted_tvs_push(K, res); + UNUSED(mp_rat_mul(K, tv2bigrat(n1), tv2bigrat(n2), tv2bigrat(res))); + krooted_tvs_pop(K); + return kbigrat_try_integer(K, res); +} + +TValue kbigrat_minus(klisp_State *K, TValue n1, TValue n2) +{ + TValue res = kbigrat_make_simple(K); + krooted_tvs_push(K, res); + UNUSED(mp_rat_sub(K, tv2bigrat(n1), tv2bigrat(n2), tv2bigrat(res))); + krooted_tvs_pop(K); + return kbigrat_try_integer(K, res); +} + +/* NOTE: n2 can't be zero, that case should be checked before calling this */ +TValue kbigrat_div_mod(klisp_State *K, TValue n1, TValue n2, TValue *res_r) +{ + /* NOTE: quotient is always an integer, remainder may be any rational */ + TValue tv_q = kbigint_make_simple(K); + krooted_tvs_push(K, tv_q); + TValue tv_r = kbigint_make_simple(K); + krooted_tvs_push(K, tv_r); + /* for temp values */ + TValue tv_true_rem = kbigrat_make_simple(K); + krooted_tvs_push(K, tv_true_rem); + TValue tv_div = kbigrat_make_simple(K); + krooted_tvs_push(K, tv_div); + + Bigrat *n = tv2bigrat(n1); + Bigrat *d = tv2bigrat(n2); + + Bigint *q = tv2bigint(tv_q); + Bigint *r = tv2bigint(tv_r); + + Bigrat *div = tv2bigrat(tv_div); + Bigrat *trem = tv2bigrat(tv_true_rem); + + UNUSED(mp_rat_div(K, n, d, div)); + + /* Now use the integral part as the quotient and the fractional part times + the divisor as the remainder, but then correct the remainder so that it's + always positive like in kbigint_div_and_mod */ + + UNUSED(mp_int_div(K, MP_NUMER_P(div), MP_DENOM_P(div), q, r)); + + /* NOTE: denom is positive, so div & q & r have the same sign */ + + /* first adjust the quotient if necessary, + the remainder will just fall into place after this */ + if (mp_rat_compare_zero(n) < 0) + UNUSED(mp_int_add_value(K, q, mp_rat_compare_zero(d) < 0? 1 : -1, q)); + + UNUSED(mp_rat_sub_int(K, div, q, trem)); + UNUSED(mp_rat_mul(K, trem, d, trem)); + + krooted_tvs_pop(K); + krooted_tvs_pop(K); + krooted_tvs_pop(K); + krooted_tvs_pop(K); + + *res_r = kbigrat_try_integer(K, tv_true_rem); + return kbigrat_try_integer(K, tv_q); +} + +TValue kbigrat_div0_mod0(klisp_State *K, TValue n1, TValue n2, TValue *res_r) +{ + /* NOTE: quotient is always an integer, remainder may be any rational */ + TValue tv_q = kbigint_make_simple(K); + krooted_tvs_push(K, tv_q); + TValue tv_r = kbigint_make_simple(K); + krooted_tvs_push(K, tv_r); + /* for temp values */ + TValue tv_true_rem = kbigrat_make_simple(K); + krooted_tvs_push(K, tv_true_rem); + TValue tv_div = kbigrat_make_simple(K); + krooted_tvs_push(K, tv_div); + + Bigrat *n = tv2bigrat(n1); + Bigrat *d = tv2bigrat(n2); + + Bigint *q = tv2bigint(tv_q); + Bigint *r = tv2bigint(tv_r); + + Bigrat *div = tv2bigrat(tv_div); + Bigrat *trem = tv2bigrat(tv_true_rem); + + UNUSED(mp_rat_div(K, n, d, div)); + + /* Now use the integral part as the quotient and the fractional part times + the divisor as the remainder, but then correct the remainder so that it's + in the interval [-|d/2|, |d/2|) */ + + UNUSED(mp_int_div(K, MP_NUMER_P(div), MP_DENOM_P(div), q, r)); + /* NOTE: denom is positive, so div & q & r have the same sign */ + UNUSED(mp_rat_sub_int(K, div, q, trem)); + UNUSED(mp_rat_mul(K, trem, d, trem)); + + /* NOTE: temporarily use trem as d/2 */ + TValue tv_d_2 = kbigrat_make_simple(K); + krooted_tvs_push(K, tv_d_2); + Bigrat *d_2 = tv2bigrat(tv_d_2); + TValue m2 = i2tv(2); + kensure_bigint(m2); + UNUSED(mp_rat_div_int(K, d, tv2bigint(m2), d_2)); + /* adjust remainder and quotient if necessary */ + /* first check positive side (closed part of the interval) */ + mp_rat_abs(K, d_2, d_2); + + /* the case analysis is like in bigint (and inverse to that of fixint) */ + if (mp_rat_compare(K, trem, d_2) >= 0) { + if (mp_rat_compare_zero(d) < 0) { + mp_rat_add(K, trem, d, trem); + mp_int_sub_value(K, q, 1, q); + } else { + mp_rat_sub(K, trem, d, trem); + mp_int_add_value(K, q, 1, q); + } + } else { + /* now check negative side (open part of the interval) */ + mp_rat_neg(K, d_2, d_2); + if (mp_rat_compare(K, trem, d_2) < 0) { + if (mp_rat_compare_zero(d) < 0) { + mp_rat_sub(K, trem, d, trem); + mp_int_add_value(K, q, 1, q); + } else { + mp_rat_add(K, trem, d, trem); + mp_int_sub_value(K, q, 1, q); + } + } + } + + krooted_tvs_pop(K); /* d/2 */ + + krooted_tvs_pop(K); + krooted_tvs_pop(K); + krooted_tvs_pop(K); + krooted_tvs_pop(K); + + *res_r = kbigrat_try_integer(K, tv_true_rem); + return kbigrat_try_integer(K, tv_q); +} + + +TValue kbigrat_divided(klisp_State *K, TValue n1, TValue n2) +{ + TValue res = kbigrat_make_simple(K); + krooted_tvs_push(K, res); + UNUSED(mp_rat_div(K, tv2bigrat(n1), tv2bigrat(n2), tv2bigrat(res))); + krooted_tvs_pop(K); + return kbigrat_try_integer(K, res); +} + +bool kbigrat_negativep(TValue tv_bigrat) +{ + return (mp_rat_compare_zero(tv2bigrat(tv_bigrat)) < 0); +} + +bool kbigrat_positivep(TValue tv_bigrat) +{ + return (mp_rat_compare_zero(tv2bigrat(tv_bigrat)) > 0); +} + +/* GC: These assume tv_bigrat is rooted */ +/* needs the state to create a copy if negative */ +TValue kbigrat_abs(klisp_State *K, TValue tv_bigrat) +{ + if (kbigrat_negativep(tv_bigrat)) { + TValue copy = kbigrat_make_simple(K); + krooted_tvs_push(K, copy); + UNUSED(mp_rat_abs(K, tv2bigrat(tv_bigrat), tv2bigrat(copy))); + krooted_tvs_pop(K); + /* NOTE: this can never be an integer if the parameter was a bigrat */ + return copy; + } else { + return tv_bigrat; + } +} + +TValue kbigrat_numerator(klisp_State *K, TValue tv_bigrat) +{ + int32_t fnum = 0; + Bigrat *bigrat = tv2bigrat(tv_bigrat); + if (mp_rat_to_ints(bigrat, &fnum, NULL) == MP_OK) + return i2tv(fnum); + else { + TValue copy = kbigint_make_simple(K); + krooted_tvs_push(K, copy); + UNUSED(mp_rat_numer(K, bigrat, tv2bigint(copy))); + krooted_tvs_pop(K); + /* NOTE: may still be a fixint because mp_rat_to_ints fails if + either numer or denom isn't a fixint */ + return kbigint_try_fixint(K, copy); + } +} + +TValue kbigrat_denominator(klisp_State *K, TValue tv_bigrat) +{ + int32_t fden = 0; + Bigrat *bigrat = tv2bigrat(tv_bigrat); + if (mp_rat_to_ints(bigrat, NULL, &fden) == MP_OK) + return i2tv(fden); + else { + TValue copy = kbigint_make_simple(K); + krooted_tvs_push(K, copy); + UNUSED(mp_rat_denom(K, bigrat, tv2bigint(copy))); + krooted_tvs_pop(K); + /* NOTE: may still be a fixint because mp_rat_to_ints fails if + either numer or denom isn't a fixint */ + return kbigint_try_fixint(K, copy); + } +} + +TValue kbigrat_to_integer(klisp_State *K, TValue tv_bigrat, kround_mode mode) +{ + /* do an usigned divide first */ + TValue tv_quot = kbigint_make_simple(K); + krooted_tvs_push(K, tv_quot); + TValue tv_rest = kbigint_make_simple(K); + krooted_tvs_push(K, tv_rest); + Bigint *quot = tv2bigint(tv_quot); + Bigint *rest = tv2bigint(tv_rest); + Bigrat *n = tv2bigrat(tv_bigrat); + + UNUSED(mp_int_abs(K, MP_NUMER_P(n), quot)); + UNUSED(mp_int_div(K, quot, MP_DENOM_P(n), quot, rest)); + + if (mp_rat_compare_zero(n) < 0) + UNUSED(mp_int_neg(K, quot, quot)); + + switch(mode) { + case K_TRUNCATE: + /* nothing needs to be done */ + break; + case K_CEILING: + if (mp_rat_compare_zero(n) > 0 && mp_int_compare_zero(rest) != 0) + UNUSED(mp_int_add_value(K, quot, 1, quot)); + break; + case K_FLOOR: + if (mp_rat_compare_zero(n) < 0 && mp_int_compare_zero(rest) != 0) + UNUSED(mp_int_sub_value(K, quot, 1, quot)); + break; + case K_ROUND_EVEN: + UNUSED(mp_int_mul_pow2(K, rest, 1, rest)); + if (mp_int_compare(rest, MP_DENOM_P(n)) == 0 && + mp_int_is_odd(quot)) + UNUSED(mp_int_add_value(K, quot, mp_rat_compare_zero(n) < 0? + -1 : 1, quot)); + break; + } + + krooted_tvs_pop(K); + krooted_tvs_pop(K); + return kbigint_try_fixint(K, tv_quot); +} + +/* +** SOURCE NOTE: this implementation is from the Haskell 98 report +*/ +/* +approxRational x eps = simplest (x-eps) (x+eps) + where simplest x y | y < x = simplest y x + | x == y = xr + | x > 0 = simplest' n d n' d' + | y < 0 = - simplest' (-n') d' (-n) d + | otherwise = 0 :% 1 + where xr@(n:%d) = toRational x + (n':%d') = toRational y + + simplest' n d n' d' -- assumes 0 < n%d < n'%d' + | r == 0 = q :% 1 + | q /= q' = (q+1) :% 1 + | otherwise = (q*n''+d'') :% n'' + where (q,r) = quotRem n d + (q',r') = quotRem n' d' + (n'':%d'') = simplest' d' r' d r + +*/ + +/* +** NOTE: this reads almost like a Haskell commercial. +** The c code is an order of magnitude longer. Some of this has to do +** with the representation of values, some because this is iterative, +** some because of GC rooting, some because of lack of powerful pattern +** matching, and so on, and so on +*/ + +/* Assumes 0 < n1/d1 < n2/d2 */ +/* GC: Assumes n1, d1, n2, d2, and res are fresh (can be mutated) and rooted */ +static void simplest(klisp_State *K, TValue tv_n1, TValue tv_d1, + TValue tv_n2, TValue tv_d2, TValue tv_res) +{ + Bigint *n1 = tv2bigint(tv_n1); + Bigint *d1 = tv2bigint(tv_d1); + Bigint *n2 = tv2bigint(tv_n2); + Bigint *d2 = tv2bigint(tv_d2); + + Bigrat *res = tv2bigrat(tv_res); + + /* create vars q1, r1, q2 & r2 */ + TValue tv_q1 = kbigint_make_simple(K); + krooted_tvs_push(K, tv_q1); + Bigint *q1 = tv2bigint(tv_q1); + + TValue tv_r1 = kbigint_make_simple(K); + krooted_tvs_push(K, tv_r1); + Bigint *r1 = tv2bigint(tv_r1); + + TValue tv_q2 = kbigint_make_simple(K); + krooted_tvs_push(K, tv_q2); + Bigint *q2 = tv2bigint(tv_q2); + + TValue tv_r2 = kbigint_make_simple(K); + krooted_tvs_push(K, tv_r2); + Bigint *r2 = tv2bigint(tv_r2); + + while(true) { + UNUSED(mp_int_div(K, n1, d1, q1, r1)); + UNUSED(mp_int_div(K, n2, d2, q2, r2)); + + if (mp_int_compare_zero(r1) == 0) { + /* res = q1 / 1 */ + mp_rat_zero(K, res); + mp_rat_add_int(K, res, q1, res); + break; + } else if (mp_int_compare(q1, q2) != 0) { + /* res = (q1 + 1) / 1 */ + mp_rat_zero(K, res); + mp_int_add_value(K, q1, 1, q1); + mp_rat_add_int(K, res, q1, res); + break; + } else { + /* simulate a recursive call */ + TValue saved_q1 = kbigint_make_simple(K); + krooted_tvs_push(K, saved_q1); + UNUSED(mp_int_copy(K, q1, tv2bigint(saved_q1))); + ks_spush(K, saved_q1); + krooted_tvs_pop(K); + + UNUSED(mp_int_copy(K, d2, n1)); + UNUSED(mp_int_copy(K, d1, n2)); + UNUSED(mp_int_copy(K, r2, d1)); + UNUSED(mp_int_copy(K, r1, d2)); + } /* fall through */ + } + + /* now, if there were "recursive" calls, complete them */ + while(!ks_sisempty(K)) { + TValue saved_q1 = ks_sget(K); + TValue tv_tmp = kbigrat_make_simple(K); + krooted_tvs_push(K, tv_tmp); + Bigrat *tmp = tv2bigrat(tv_tmp); + + UNUSED(mp_rat_copy(K, res, tmp)); + /* res = (saved_q * n(res)) + d(res)) / n(res) */ + UNUSED(mp_rat_zero(K, res)); + UNUSED(mp_rat_add_int(K, res, tv2bigint(saved_q1), res)); + UNUSED(mp_rat_mul_int(K, res, MP_NUMER_P(tmp), res)); + UNUSED(mp_rat_add_int(K, res, MP_DENOM_P(tmp), res)); + UNUSED(mp_rat_div_int(K, res, MP_NUMER_P(tmp), res)); + krooted_tvs_pop(K); /* tmp */ + ks_sdpop(K); /* saved_q1 */ + } + + krooted_tvs_pop(K); /* q1, r1, q2, r2 */ + krooted_tvs_pop(K); + krooted_tvs_pop(K); + krooted_tvs_pop(K); + + return; +} + +TValue kbigrat_simplest_rational(klisp_State *K, TValue tv_n1, TValue tv_n2) +{ + TValue tv_res = kbigrat_make_simple(K); + krooted_tvs_push(K, tv_res); + Bigrat *res = tv2bigrat(tv_res); + Bigrat *n1 = tv2bigrat(tv_n1); + Bigrat *n2 = tv2bigrat(tv_n2); + + int32_t cmp = mp_rat_compare(K, n1, n2); + if (cmp > 0) { /* n1 > n2, swap */ + TValue temp = tv_n1; + tv_n1 = tv_n2; + tv_n2 = temp; + n1 = tv2bigrat(tv_n1); + n2 = tv2bigrat(tv_n2); + /* fall through */ + } else if (cmp == 0) { /* n1 == n2 */ + krooted_tvs_pop(K); + return tv_n1; + } /* else fall through */ + + /* we now know that n1 < n2 */ + if (mp_rat_compare_zero(n1) > 0) { + /* 0 > n1 > n2 */ + TValue num1 = kbigint_make_simple(K); + krooted_tvs_push(K, num1); + UNUSED(mp_rat_numer(K, n1, tv2bigint(num1))); + + TValue den1 = kbigint_make_simple(K); + krooted_tvs_push(K, den1); + UNUSED(mp_rat_denom(K, n1, tv2bigint(den1))); + + TValue num2 = kbigint_make_simple(K); + krooted_tvs_push(K, num2); + UNUSED(mp_rat_numer(K, n2, tv2bigint(num2))); + + TValue den2 = kbigint_make_simple(K); + krooted_tvs_push(K, den2); + UNUSED(mp_rat_denom(K, n2, tv2bigint(den2))); + + simplest(K, num1, den1, num2, den2, tv_res); + + krooted_tvs_pop(K); /* num1, num2, den1, den2 */ + krooted_tvs_pop(K); + krooted_tvs_pop(K); + krooted_tvs_pop(K); + + krooted_tvs_pop(K); /* tv_res */ + return kbigrat_try_integer(K, tv_res); + } else if (mp_rat_compare_zero(n2) < 0) { + /* n1 < n2 < 0 */ + + /* do -(simplest -n2/d2 -n1/d1) */ + + TValue num1 = kbigint_make_simple(K); + krooted_tvs_push(K, num1); + UNUSED(mp_int_neg(K, MP_NUMER_P(n2), tv2bigint(num1))); + + TValue den1 = kbigint_make_simple(K); + krooted_tvs_push(K, den1); + UNUSED(mp_rat_denom(K, n2, tv2bigint(den1))); + + TValue num2 = kbigint_make_simple(K); + krooted_tvs_push(K, num2); + UNUSED(mp_int_neg(K, MP_NUMER_P(n1), tv2bigint(num2))); + + TValue den2 = kbigint_make_simple(K); + krooted_tvs_push(K, den2); + UNUSED(mp_rat_denom(K, n1, tv2bigint(den2))); + + simplest(K, num1, den1, num2, den2, tv_res); + mp_rat_neg(K, res, res); + + krooted_tvs_pop(K); /* num1, num2, den1, den2 */ + krooted_tvs_pop(K); + krooted_tvs_pop(K); + krooted_tvs_pop(K); + + krooted_tvs_pop(K); /* tv_res */ + return kbigrat_try_integer(K, tv_res); + } else { + /* n1 < 0 < n2 */ + krooted_tvs_pop(K); + return i2tv(0); + } +} + +TValue kbigrat_rationalize(klisp_State *K, TValue tv_n1, TValue tv_n2) +{ + /* delegate all work to simplest_rational */ + TValue tv_min = kbigrat_make_simple(K); + krooted_tvs_push(K, tv_min); + TValue tv_max = kbigrat_make_simple(K); + krooted_tvs_push(K, tv_max); + + Bigrat *n1 = tv2bigrat(tv_n1); + Bigrat *n2 = tv2bigrat(tv_n2); + /* it doesn't matter if these are reversed */ + Bigrat *min = tv2bigrat(tv_min); + Bigrat *max = tv2bigrat(tv_max); + + UNUSED(mp_rat_sub(K, n1, n2, min)); + UNUSED(mp_rat_add(K, n1, n2, max)); + + TValue res = kbigrat_simplest_rational(K, tv_min, tv_max); + + krooted_tvs_pop(K); + krooted_tvs_pop(K); + + return res; +} diff --git a/src/krational.h b/src/krational.h @@ -0,0 +1,172 @@ +/* +** krational.h +** Kernel Rationals (fixrats and bigrats) +** See Copyright Notice in klisp.h +*/ + +#ifndef krational_h +#define krational_h + +#include <stdbool.h> +#include <stdint.h> +#include <inttypes.h> + +#include "kobject.h" +#include "kstate.h" +#include "kinteger.h" +#include "imrat.h" + +/* TEMP: for now we only implement bigrats (memory allocated) */ + +/* This tries to convert a bigrat to a fixint or a bigint */ +inline TValue kbigrat_try_integer(klisp_State *K, TValue n) +{ + Bigrat *b = tv2bigrat(n); + + if (!mp_rat_is_integer(b)) + return n; + + /* sadly we have to repeat the code from try_fixint here... */ + Bigint *i = MP_NUMER_P(b); + if (MP_USED(i) == 1) { + int64_t digit = (int64_t) *(MP_DIGITS(i)); + if (MP_SIGN(i) == MP_NEG) digit = -digit; + if (kfit_int32_t(digit)) + return i2tv((int32_t) digit); + /* else fall through */ + } + /* should alloc a bigint */ + /* GC: n may not be rooted */ + krooted_tvs_push(K, n); + TValue copy = kbigint_copy(K, gc2bigint(i)); + krooted_tvs_pop(K); + return copy; +} + +/* used in reading and for res & temps in operations */ +TValue kbigrat_new(klisp_State *K, bool sign, uint32_t num, + uint32_t den); + +/* used in write to destructively get the digits */ +TValue kbigrat_copy(klisp_State *K, TValue src); + +/* macro to create the simplest rational */ +#define kbigrat_make_simple(K_) kbigrat_new(K_, false, 0, 1) + +/* Create a stack allocated bigrat from a bigint, + useful for mixed operations, relatively light weight compared + to creating it in the heap and burdening the gc */ +#define kbind_bigrat_fixint(name, fixint) \ + int32_t (KUNIQUE_NAME(i)) = ivalue(fixint); \ + Bigrat KUNIQUE_NAME(bigrat_i); \ + /* can't use unique_name bigrat because it conflicts */ \ + /* numer is 1 */ \ + (KUNIQUE_NAME(bigrat_i)).num.single = ({ \ + int64_t temp = (KUNIQUE_NAME(i)); \ + (uint32_t) ((temp < 0)? -temp : temp); \ + }); \ + (KUNIQUE_NAME(bigrat_i)).num.digits = \ + &((KUNIQUE_NAME(bigrat_i)).num.single); \ + (KUNIQUE_NAME(bigrat_i)).num.alloc = 1; \ + (KUNIQUE_NAME(bigrat_i)).num.used = 1; \ + (KUNIQUE_NAME(bigrat_i)).num.sign = (KUNIQUE_NAME(i)) < 0? \ + MP_NEG : MP_ZPOS; \ + /* denom is 1 */ \ + (KUNIQUE_NAME(bigrat_i)).den.single = 1; \ + (KUNIQUE_NAME(bigrat_i)).den.digits = \ + &((KUNIQUE_NAME(bigrat_i)).den.single); \ + (KUNIQUE_NAME(bigrat_i)).den.alloc = 1; \ + (KUNIQUE_NAME(bigrat_i)).den.used = 1; \ + (KUNIQUE_NAME(bigrat_i)).den.sign = MP_ZPOS; \ + \ + Bigrat *name = &(KUNIQUE_NAME(bigrat_i)) + +#define kbind_bigrat_bigint(name, bigint) \ + Bigint *KUNIQUE_NAME(bi) = tv2bigint(bigint); \ + Bigrat KUNIQUE_NAME(bigrat); \ + /* numer is bigint */ \ + (KUNIQUE_NAME(bigrat)).num.single = (KUNIQUE_NAME(bi))->single; \ + (KUNIQUE_NAME(bigrat)).num.digits = (KUNIQUE_NAME(bi))->digits; \ + (KUNIQUE_NAME(bigrat)).num.alloc = (KUNIQUE_NAME(bi))->alloc; \ + (KUNIQUE_NAME(bigrat)).num.used = (KUNIQUE_NAME(bi))->used; \ + (KUNIQUE_NAME(bigrat)).num.sign = (KUNIQUE_NAME(bi))->sign; \ + /* denom is 1 */ \ + (KUNIQUE_NAME(bigrat)).den.single = 1; \ + (KUNIQUE_NAME(bigrat)).den.digits = \ + &((KUNIQUE_NAME(bigrat)).den.single); \ + (KUNIQUE_NAME(bigrat)).den.alloc = 1; \ + (KUNIQUE_NAME(bigrat)).den.used = 1; \ + (KUNIQUE_NAME(bigrat)).den.sign = MP_ZPOS; \ + Bigrat *name = &(KUNIQUE_NAME(bigrat)) + +/* XXX: Now that I think about it this (and kensure_bigint) could be more + cleanly implemented as a function that takes a pointer... (derp derp) */ + +/* This can be used prior to calling a bigrat functions + to automatically convert fixints & bigints to bigrats. + NOTE: calls to this macro should go in different lines! + and on different lines to calls to kensure_bigint */ +#define kensure_bigrat(n) \ + /* must use goto, no block should be entered before calling \ + kbind_bigrat */ \ + if (ttisbigrat(n)) \ + goto KUNIQUE_NAME(bigrat_exit_lbl); \ + if (ttisbigint(n)) \ + goto KUNIQUE_NAME(bigrat_bigint_lbl); \ + /* else ttisfixint(n) */ \ + kbind_bigrat_fixint(KUNIQUE_NAME(brat_i), (n)); \ + (n) = gc2bigrat(KUNIQUE_NAME(brat_i)); \ + goto KUNIQUE_NAME(bigrat_exit_lbl); \ +KUNIQUE_NAME(bigrat_bigint_lbl): \ + ; /* gcc asks for a statement (not a decl) after label */ \ + kbind_bigrat_bigint(KUNIQUE_NAME(brat), (n)); \ + (n) = gc2bigrat(KUNIQUE_NAME(brat)); \ +KUNIQUE_NAME(bigrat_exit_lbl): + +/* +** read/write interface +*/ +/* this works for bigrats, bigints & fixints, returns true if ok */ +/* NOTE: doesn't allow decimal */ +bool krational_read(klisp_State *K, char *buf, int32_t base, TValue *out, + char **end); +/* NOTE: allow decimal for use after #e */ +bool krational_read_decimal(klisp_State *K, char *buf, int32_t base, TValue *out, + char **end); + +int32_t kbigrat_print_size(TValue tv_bigrat, int32_t base); +void kbigrat_print_string(klisp_State *K, TValue tv_bigrat, int32_t base, + char *buf, int32_t limit); + +/* Interface for kgnumbers */ +bool kbigrat_eqp(klisp_State *K, TValue bigrat1, TValue bigrat2); + +bool kbigrat_ltp(klisp_State *K, TValue bigrat1, TValue bigrat2); +bool kbigrat_lep(klisp_State *K, TValue bigrat1, TValue bigrat2); +bool kbigrat_gtp(klisp_State *K, TValue bigrat1, TValue bigrat2); +bool kbigrat_gep(klisp_State *K, TValue bigrat1, TValue bigrat2); + +TValue kbigrat_plus(klisp_State *K, TValue n1, TValue n2); +TValue kbigrat_times(klisp_State *K, TValue n1, TValue n2); +TValue kbigrat_minus(klisp_State *K, TValue n1, TValue n2); +TValue kbigrat_divided(klisp_State *K, TValue n1, TValue n2); + +TValue kbigrat_div_mod(klisp_State *K, TValue n1, TValue n2, TValue *res_r); +TValue kbigrat_div0_mod0(klisp_State *K, TValue n1, TValue n2, TValue *res_r); + +bool kbigrat_negativep(TValue tv_bigrat); +bool kbigrat_positivep(TValue tv_bigrat); + +/* needs the state to create a copy if negative */ +TValue kbigrat_abs(klisp_State *K, TValue tv_bigrat); + +TValue kbigrat_numerator(klisp_State *K, TValue tv_bigrat); +TValue kbigrat_denominator(klisp_State *K, TValue tv_bigrat); + +typedef enum { K_FLOOR, K_CEILING, K_TRUNCATE, K_ROUND_EVEN } kround_mode; +TValue kbigrat_to_integer(klisp_State *K, TValue tv_bigrat, kround_mode mode); + +TValue kbigrat_simplest_rational(klisp_State *K, TValue tv_n1, TValue tv_n2); +TValue kbigrat_rationalize(klisp_State *K, TValue tv_n1, TValue tv_n2); + +#endif diff --git a/src/ktoken.c b/src/ktoken.c @@ -13,8 +13,9 @@ ** TODO: ** ** From the Report: -** - Support other number types besides integers and exact infinities -** - Support for complete number syntax (inexacts, rationals, reals, complex) +** - Support other number types besides integers, rationals and exact +** infinities +** - Support for complete number syntax (inexacts, reals, complex) ** ** NOT from the Report: ** - Support for unicode (strings, char and symbols). @@ -36,6 +37,7 @@ #include "kobject.h" #include "kstate.h" #include "kinteger.h" +#include "krational.h" #include "kpair.h" #include "kstring.h" #include "ksymbol.h" @@ -393,72 +395,29 @@ int32_t ktok_read_until_delimiter(klisp_State *K) ** The digits are in buf, that must be freed after use, ** len should be at least one */ -TValue ktok_read_number(klisp_State *K, char *buf, int32_t len, +TValue ktok_read_number(klisp_State *K, char *buf, int32_t len, bool has_exactp, bool exactp, bool has_radixp, int32_t radix) { - /* TODO use IMATH library to do this */ - uint32_t fixint_res = 0; - bool is_fixint = true; - TValue bigint_res; - - int32_t i = 0; - bool is_pos = true; - /* first check the sign */ - if (buf[i] == '+' || buf[i] == '-') { - is_pos = (buf[i] == '+'); - ++i; - if (i == len) { - ktok_error(K, "No digit found in number"); - /* avoid warning */ + UNUSED(len); /* not needed really, buf ends with '\0' */ + TValue n; + if (has_exactp && radix == 10) { + /* TEMP: while there are no inexacts */ + /* allow decimals if has #e prefix */ + if (!krational_read_decimal(K, buf, radix, &n, NULL)) { + /* TODO throw meaningful error msgs, use last param */ + ktok_error(K, "Bad format in number"); return KINERT; } - } - - while(i < len) { - char ch = buf[i++]; - - if (!ktok_is_digit(ch, radix)) { - /* TODO show the char */ - if (ktok_is_digit(ch, 16)) { - ktok_error(K, "Invalid digit in this radix"); - return KINERT; - } else { - ktok_error(K, "Invalid char found in number"); - return KINERT; - } - } - int32_t new_digit = ktok_digit_value(ch); - - if (is_fixint && can_add_digit(fixint_res, !is_pos, new_digit, - radix)) { - fixint_res = fixint_res * radix + new_digit; - } else { - if (is_fixint) { - /* up to the last loop was fixint, but can't be anymore. - Create a bigint and mutate to add the new digits. This - avoids unnecessary consing and discarding values that would - occur if it used the regular bigint+ and bigint* */ - is_fixint = false; - bigint_res = kbigint_new(K, false, fixint_res); - krooted_vars_push(K, &bigint_res); - } - kbigint_add_digit(K, bigint_res, radix, new_digit); + } else { + if (!krational_read(K, buf, radix, &n, NULL)) { + /* TODO throw meaningful error msgs, use last param */ + ktok_error(K, "Bad format in number"); + return KINERT; } } - ks_tbclear(K); - - if (is_fixint) { - int32_t fixint = (is_pos)? (int32_t) fixint_res : - (int32_t) -((int64_t) fixint_res); - return i2tv(fixint); - } else { - if (!is_pos) - kbigint_invert_sign(K, bigint_res); - krooted_vars_pop(K); - return bigint_res; - } + return n; } TValue ktok_read_maybe_signed_numeric(klisp_State *K) @@ -649,34 +608,33 @@ TValue ktok_read_special(klisp_State *K) token, or a char constant or a number. srfi-38 tokens are a '#' a decimal number and end with a '=' or a '#' */ if (buf_len > 2 && ktok_is_numeric(buf[1])) { + /* NOTE: it's important to check is_numeric to avoid problems with + sign in kinteger_read */ /* srfi-38 type token (can be either a def or ref) */ + /* TODO: lift this implementation restriction */ /* IMPLEMENTATION RESTRICTION: only allow fixints in shared tokens */ - int32_t res = 0; - int32_t i = 1; - char ch = buf[i]; - while(i < buf_len && ch != '#' && ch != '=') { - if (!ktok_is_numeric(ch)) { - ktok_error(K, "Invalid char found in srfi-38 token"); - /* avoid warning */ - return KINERT; - } + char ch = buf[buf_len-1]; /* remember last char */ + buf[buf_len-1] = '\0'; /* replace last char with 0 to read number */ - int new_digit = ktok_digit_value(ch); - if (can_add_digit(res, false, new_digit, 10)) { - res = res * 10 + new_digit; - } else { - ktok_error(K, "IMP. RESTRICTION: shared token too big"); - /* avoid warning */ - return KINERT; - } - ch = buf[++i]; - } - if (i == buf_len) { + if (ch != '#' && ch != '=') { ktok_error(K, "Missing last char in srfi-38 token"); return KINERT; } /* else buf[i] == '#' or '=' */ + TValue n; + char *end; + /* 10 is the radix for srfi-38 tokens, buf+1 to jump over the '#', + end+1 to count the last char */ + if (!kinteger_read(K, buf+1, 10, &n, &end) || end+1 - buf != buf_len) { + ktok_error(K, "Bad char in srfi-38 token"); + return KINERT; + } else if (!ttisfixint(n)) { + ktok_error(K, "IMP. RESTRICTION: shared token too big"); + /* avoid warning */ + return KINERT; + } ks_tbclear(K); - return kcons(K, ch2tv(ch), i2tv(res)); + /* GC: no need to root n, for now it's a fixint */ + return kcons(K, ch2tv(ch), n); } /* REFACTOR: move to new function */ diff --git a/src/kwrite.c b/src/kwrite.c @@ -12,6 +12,7 @@ #include "kwrite.h" #include "kobject.h" #include "kinteger.h" +#include "krational.h" #include "kpair.h" #include "kstring.h" #include "ksymbol.h" @@ -52,40 +53,41 @@ void kwrite_error(klisp_State *K, char *msg) } /* TODO: check for return codes and throw error if necessary */ - +#define KDEFAULT_NUMBER_RADIX 10 void kw_print_bigint(klisp_State *K, TValue bigint) { - int32_t size = kbigint_print_size(bigint, 10) + - ((kbigint_negativep(bigint))? 1 : 0); - + int32_t radix = KDEFAULT_NUMBER_RADIX; + int32_t size = kbigint_print_size(bigint, radix); krooted_tvs_push(K, bigint); + /* here we are using 1 byte extra, because size already includes + 1 for the terminator, but better be safe than sorry */ TValue buf_str = kstring_new_s(K, size); krooted_tvs_push(K, buf_str); - /* write backwards so we can use printf later */ - char *buf = kstring_buf(buf_str) + size - 1; - - TValue copy = kbigint_copy(K, bigint); - krooted_vars_push(K, &copy); + char *buf = kstring_buf(buf_str); + kbigint_print_string(K, bigint, radix, buf, size); + kw_printf(K, "%s", buf); - /* must work with positive bigint to get the digits */ - if (kbigint_negativep(bigint)) - kbigint_invert_sign(K, copy); + krooted_tvs_pop(K); + krooted_tvs_pop(K); +} - while(kbigint_has_digits(K, copy)) { - int32_t digit = kbigint_remove_digit(K, copy, 10); - /* write backwards so we can use printf later */ - /* XXX: use to_digit function */ - *buf-- = '0' + digit; - } - if (kbigint_negativep(bigint)) - *buf-- = '-'; +void kw_print_bigrat(klisp_State *K, TValue bigrat) +{ + int32_t radix = KDEFAULT_NUMBER_RADIX; + int32_t size = kbigrat_print_size(bigrat, radix); + krooted_tvs_push(K, bigrat); + /* here we are using 1 byte extra, because size already includes + 1 for the terminator, but better be safe than sorry */ + TValue buf_str = kstring_new_s(K, size); + krooted_tvs_push(K, buf_str); - kw_printf(K, "%s", buf+1); + char *buf = kstring_buf(buf_str); + kbigrat_print_string(K, bigrat, radix, buf, size); + kw_printf(K, "%s", buf); krooted_tvs_pop(K); krooted_tvs_pop(K); - krooted_vars_pop(K); } /* @@ -264,6 +266,9 @@ void kwrite_simple(klisp_State *K, TValue obj) case K_TBIGINT: kw_print_bigint(K, obj); break; + case K_TBIGRAT: + kw_print_bigrat(K, obj); + break; case K_TNIL: kw_printf(K, "()"); break;