klisp

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

commit 4df6bc72e51871dbbac36e5cc6b0dd0d416d8c58
parent a788c5f12ecaaef3b8b7a2d02911aa3e1ca3212a
Author: Andres Navarro <canavarro82@gmail.com>
Date:   Mon, 11 Apr 2011 23:58:13 -0300

Changed typedef in imath.h to use Bigint (from kobject.h). Added kobject & kstate includes in imath.h. Removed all bigint code from kinteger.

Diffstat:
Msrc/Makefile | 4++--
Msrc/imath.h | 9++++++++-
Msrc/kinteger.c | 209+++++++++++--------------------------------------------------------------------
Msrc/kinteger.h | 8+++++++-
Msrc/kobject.h | 118++++---------------------------------------------------------------------------
Msrc/kstate.c | 7+------
6 files changed, 51 insertions(+), 304 deletions(-)

diff --git a/src/Makefile b/src/Makefile @@ -139,4 +139,4 @@ kgnumbers.o: kgnumbers.c kgnumbers.h kghelpers.h kstate.h klisp.h \ kgstrings.o: kgstrings.c kgstrings.h kghelpers.h kstate.h klisp.h \ kobject.h kerror.h kapplicative.h koperative.h kcontinuation.h \ ksymbol.h -imath.o: -\ No newline at end of file +imath.o: kobject.h kstate.h +\ No newline at end of file diff --git a/src/imath.h b/src/imath.h @@ -21,6 +21,10 @@ #define USE_C99 1 #endif +/* Andres Navarro: klisp includes */ +#include "kobject.h" +#include "kstate.h" + #ifdef USE_C99 #include <stdint.h> #endif @@ -52,7 +56,8 @@ typedef unsigned int mp_word; #endif /* USE_LONG_LONG */ #endif /* USE_C99 */ - +/* Andres Navarro: Use kobject type instead */ +/* typedef struct mpz { mp_digit single; mp_digit *digits; @@ -60,6 +65,8 @@ typedef struct mpz { mp_size used; mp_sign sign; } mpz_t, *mp_int; +*/ +typedef Bigint mpz_t, *mp_int; #define MP_DIGITS(Z) ((Z)->digits) #define MP_ALLOC(Z) ((Z)->alloc) diff --git a/src/kinteger.c b/src/kinteger.c @@ -14,21 +14,6 @@ #include "kstate.h" #include "kmem.h" -#define bind_iter kbind_bigint_iter -#define iter_has_next kbigint_iter_has_more -#define iter_next kbigint_iter_next -#define iter_update_last kbigint_iter_update_last - -#define LOG_BASE(base) (log(2.0) / log(base)) - -Bigint_Node *make_new_node(klisp_State *K, uint32_t digit) -{ - Bigint_Node *node = klispM_new(K, Bigint_Node); - node->digit = digit; - node->next_xor_prev = (uintptr_t) 0; /* NULL ^ NULL: 0 */ - return node; -} - /* for now used only for reading */ /* NOTE: is uint to allow INT32_MIN as positive argument in read */ TValue kbigint_new(klisp_State *K, bool sign, uint32_t digit) @@ -47,12 +32,8 @@ TValue kbigint_new(klisp_State *K, bool sign, uint32_t digit) /* GC: root bigint */ /* put dummy value to work if garbage collections happens while allocating node */ - new_bigint->sign_size = 0; - new_bigint->first = new_bigint->last = NULL; - Bigint_Node *node = make_new_node(K, digit); - new_bigint->first = new_bigint->last = node; - new_bigint->sign_size = sign? -1 : 1; + /* TODO */ return gc2bigint(new_bigint); } @@ -60,20 +41,8 @@ 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) { - Bigint *srcb = tv2bigint(src); - /* iterate in little endian mode */ - bind_iter(iter, srcb, false); - uint32_t digit = iter_next(iter); - /* GC: root copy */ - TValue copy = kbigint_new(K, kbigint_sign(srcb), digit); - Bigint *copyb = tv2bigint(copy); - - while(iter_has_next(iter)) { - uint32_t digit = iter_next(iter); - kbigint_add_node(copyb, make_new_node(K, digit)); - } - - return copy; + /* XXX / TODO */ + return src; } /* This algorithm is like a fused multiply add on bignums, @@ -82,173 +51,51 @@ TValue kbigint_copy(klisp_State *K, TValue src) void kbigint_add_digit(klisp_State *K, TValue tv_bigint, int32_t base, int32_t digit) { - Bigint *bigint = tv2bigint(tv_bigint); - /* iterate in little endian mode */ - bind_iter(iter, bigint, false); - - uint64_t carry = digit; - - while(iter_has_next(iter)) { - uint32_t cur = iter_next(iter); - /* I hope the compiler understand that this should be a - 32bits x 32bits = 64bits multiplication instruction */ - uint64_t res_carry = (uint64_t) cur * base + carry; - carry = res_carry >> 32; - uint32_t new_cur = (uint32_t) res_carry; - iter_update_last(iter, new_cur); - } - - if (carry != 0) { - /* must add one node to the bigint */ - kbigint_add_node(bigint, make_new_node(K, (uint32_t) carry)); - } + /* XXX / TODO */ + return; } /* This is used by the writer to get the digits of a number tv_bigint must be positive */ int32_t kbigint_remove_digit(klisp_State *K, TValue tv_bigint, int32_t base) { - assert(kbigint_has_digits(K, tv_bigint)); - - Bigint *bigint = tv2bigint(tv_bigint); - - /* iterate in big endian mode */ - bind_iter(iter, bigint, true); - - uint32_t result = 0; - uint32_t rest = 0; - uint32_t divisor = base; - - while(iter_has_next(iter)) { - uint64_t dividend = (((uint64_t) rest) << 32) | - (uint64_t) iter_next(iter); - - if (dividend >= divisor) { /* avoid division if possible */ - /* I hope the compiler calculates this only once and - is able to get that this is a 64bits by 32bits division - instruction */ - result = (uint32_t) (dividend / divisor); - rest = (uint32_t) (dividend % divisor); - } else { - result = 0; - rest = (uint32_t) dividend; - } - iter_update_last(iter, result); - } - - /* rest now contains the last digit & result the value of the top node */ - - /* adjust the node list, at most the bigint should lose a node */ - if (bigint->first->digit == 0) { - Bigint_Node *node = kbigint_remove_node(bigint); - klispM_free(K, node); - } - - return (int32_t) rest; + /* XXX / TODO */ + return 0; } /* 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 kbigint_size(tv2bigint(tv_bigint)) != 0; + /* XXX / TODO */ + return false; } /* Mutate the bigint to have the opposite sign, used in read, write and abs */ void kbigint_invert_sign(TValue tv_bigint) { - Bigint *bigint = tv2bigint(tv_bigint); - bigint->sign_size = -bigint->sign_size; + /* XXX / TODO */ + return; } /* 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) { - /* count the number of bits and estimate using the log of - the base */ - Bigint *bigint = tv2bigint(tv_bigint); - - int32_t num_bits = 0; - uint32_t first_digit = bigint->first->digit; - while(first_digit != 0) { - ++num_bits; - first_digit >>= 1; - } - num_bits += 32 * (kbigint_size(bigint)) - 2 ; - /* add 1.5 for safety */ - return (int32_t)(LOG_BASE(base) * num_bits + 1.0); + /* XXX / TODO */ + return 0; } bool kbigint_eqp(TValue tv_bigint1, TValue tv_bigint2) { - Bigint *bigint1 = tv2bigint(tv_bigint1); - Bigint *bigint2 = tv2bigint(tv_bigint2); - - if (bigint1->sign_size != bigint2->sign_size) - return false; - - /* iterate in big endian mode */ - bind_iter(iter1, bigint1, true); - bind_iter(iter2, bigint2, true); - - while(iter_has_next(iter1)) { - uint32_t digit1 = iter_next(iter1); - uint32_t digit2 = iter_next(iter2); - if (digit1 != digit2) - return false; - } - return true; + /* XXX / TODO */ + return false; } bool kbigint_ltp(TValue tv_bigint1, TValue tv_bigint2) { - Bigint *bigint1 = tv2bigint(tv_bigint1); - Bigint *bigint2 = tv2bigint(tv_bigint2); - - /* first take care of the easy sign cases */ - if (kbigint_negp(bigint1)) { - if (kbigint_posp(bigint2)) { - return true; - } else { - /* if both are negative reverse the order to compare - as positive */ - Bigint *temp = bigint1; - bigint1 = bigint2; - bigint2 = temp; - /* swap the tvalues just in case */ - TValue tv_temp = tv_bigint1; - tv_bigint1 = tv_bigint2; - tv_bigint2 = tv_temp; - } - } else if (kbigint_negp(bigint2)) { - return false; - } - - /* the the easy size cases */ - int32_t size1 = kbigint_size(bigint1); - int32_t size2 = kbigint_size(bigint2); - - if (size1 < size2) - return true; - else if (size1 > size2) - return false; - - /* size and sign equal, iterate in big endian mode */ - bind_iter(iter1, bigint1, true); - bind_iter(iter2, bigint2, true); - - while(iter_has_next(iter1) && iter_has_next(iter2)) { - uint32_t digit1 = iter_next(iter1); - uint32_t digit2 = iter_next(iter2); - if (digit1 < digit2) - return true; - else if (digit1 > digit2) - return false; - /* if equal we keep comparing */ - } - + /* XXX / TODO */ return false; } @@ -272,7 +119,8 @@ bool kbigint_gep(TValue tv_bigint1, TValue tv_bigint2) bool kbigint_negativep(TValue tv_bigint) { - return kbigint_negp(tv2bigint(tv_bigint)); + /* XXX / TODO */ + return false; } /* unlike the positive? applicative this would return true on zero, @@ -281,29 +129,26 @@ bool kbigint_negativep(TValue tv_bigint) zero returning positive in other place than in positive? */ bool kbigint_positivep(TValue tv_bigint) { - return kbigint_posp(tv2bigint(tv_bigint)); + /* XXX / TODO */ + return false; } bool kbigint_oddp(TValue tv_bigint) { - Bigint *bigint = tv2bigint(tv_bigint); - return ((bigint->last->digit) & 1) != 0; + /* XXX / TODO */ + return false; } bool kbigint_evenp(TValue tv_bigint) { - Bigint *bigint = tv2bigint(tv_bigint); - return ((bigint->last->digit) & 1) == 0; + /* XXX / TODO */ + return false; } TValue kbigint_abs(klisp_State *K, TValue tv_bigint) { - if (kbigint_positivep(tv_bigint)) { - return tv_bigint; - } else { - TValue res = kbigint_copy(K, tv_bigint); - kbigint_invert_sign(res); - return res; - } + /* XXX / TODO */ + UNUSED(K); + return tv_bigint; } diff --git a/src/kinteger.h b/src/kinteger.h @@ -21,6 +21,8 @@ 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); +/* XXX/TODO: rewrite this to use IMath */ + /* Create a stack allocated bigints from a fixint, useful for mixed operations, relatively light weight compared to creating it in the heap and burdening the gc */ @@ -39,15 +41,19 @@ TValue kbigint_copy(klisp_State *K, TValue src); (KUNIQUE_NAME(bigint)).sign_size = (KUNIQUE_NAME(i)) < 0? -1 : 1; \ Bigint *name = &(KUNIQUE_NAME(bigint)); +/* XXX/TODO: rewrite this to use IMath */ + /* This can be used prior to calling a bigint functions to automatically convert fixints to bigints. NOTE: calls to this macro should go in different lines! */ #define kensure_bigint(n) \ + (n) +/* if (ttisfixint(n)) { \ kbind_bigint(KUNIQUE_NAME(bint), n); \ n = gc2bigint(KUNIQUE_NAME(bint)); \ } - +*/ /* This is used by the reader to destructively add digits to a number tv_bigint must be positive */ void kbigint_add_digit(klisp_State *K, TValue tv_bigint, int32_t base, diff --git a/src/kobject.h b/src/kobject.h @@ -255,50 +255,16 @@ typedef __attribute__((aligned (8))) union { ** Individual heap-allocated values */ -/* -** Node Structure for the list of 'digits' in bignums. -** The node list is a xor encoded doubly linked list of big endian 'digits' -** in base 2^32. -** It is a linked list instead of say, an array because it is immutable and -** there is no need to index the list. -** It is doubly linked because some operations (like + and *) work from least -** significant to most significant and some others (like <? and >?) work the -** other way around. -** It is xor encoded because, well... I never had a chance to actually use -** this and this is a perfect example of where it is actually useful: Lists -** are to be traversed in both directions, the node is small so the space -** gain is real (2/3 the space in 32 bits, 3/5 in 64 bits) and all the code -** using the pointers is encapsulated in a (relatively) small module. -*/ - -typedef struct __attribute__ ((__packed__)) { - uint32_t digit; - uintptr_t next_xor_prev; -} Bigint_Node; - typedef struct __attribute__ ((__packed__)) { CommonHeader; - Bigint_Node *first; - Bigint_Node *last; - int32_t sign_size; +/* These are all from IMath (XXX: find a way to use mp_types directly) */ + uint32_t single; + uint32_t *digits; + uint32_t alloc; + uint32_t used; + unsigned char sign; } Bigint; -/* macros to access size/sign */ -#define kbigint_sign(b_) ((b_)->sign_size < 0) -#define kbigint_negp(b_) (kbigint_sign(b_)) -#define kbigint_posp(b_) (!kbigint_sign(b_)) -#define kbigint_size(b_) ({ int32_t ss = (b_)->sign_size; \ - ss < 0? -ss : ss;}) - -/* Java Style Iterator for the xor list */ -typedef struct { - Bigint_Node *cur; - Bigint_Node *next; -} Bigint_Iter; - -#define kxor_next(cur, prev) \ - ((Bigint_Node *) ((cur)->next_xor_prev ^ (uintptr_t) (prev))) - /* REFACTOR: move these macros somewhere else */ /* NOTE: The use of the intermediate KCONCAT is needed to allow expansion of the __LINE__ macro. */ @@ -306,78 +272,6 @@ typedef struct { #define KCONCAT(a, b) KCONCAT_(a, b) #define KUNIQUE_NAME(prefix) KCONCAT(prefix, __LINE__ ) -#define kbind_bigint_iter(name, bigint, be) \ - Bigint_Iter KUNIQUE_NAME(iter); \ - Bigint_Iter *(name) = &(KUNIQUE_NAME(iter)); \ - kbigint_iter_init((name), (bigint), (be)); - -inline void kbigint_iter_init(Bigint_Iter *i, Bigint *bigint, bool big_endian) -{ - i->cur = (Bigint_Node *) NULL; - i->next = big_endian? bigint->first : bigint->last; -} - -inline bool kbigint_iter_has_more(Bigint_Iter *i) -{ - return i->next != NULL; -} - -inline uint32_t kbigint_iter_next(Bigint_Iter *i) -{ - assert(kbigint_iter_has_more(i)); - - Bigint_Node *next_next = kxor_next(i->next, i->cur); - i->cur = i->next; - i->next = next_next; - return i->cur->digit; -} - -/* this is needed for add_digit */ -inline void kbigint_iter_update_last(Bigint_Iter *i, uint32_t digit) -{ - assert(i->cur != NULL); - i->cur->digit = digit; -} - -/* Helper for adding nodes to the head of the list. - Neither can be NULL. - The second argument should have NULL as previous for this to work */ -inline void kbigint_node_cons(Bigint_Node *head, Bigint_Node *tail) -{ - head->next_xor_prev = (uintptr_t) tail ^ (uintptr_t) NULL; - tail->next_xor_prev = (tail->next_xor_prev ^ (uintptr_t) NULL) ^ - (uintptr_t) head; -} - -/* used in add_digit, bigint has at least one node */ -inline void kbigint_add_node(Bigint *bigint, Bigint_Node *node) -{ - kbigint_node_cons(node, bigint->first); - bigint->first = node; - bigint->sign_size += bigint->sign_size < 0? -1 : 1; -} - -/* Helper for removing a node from the head of the list. - The argument should have NULL as previous for this to work */ -inline Bigint_Node *kbigint_remove_node(Bigint *bigint) -{ - Bigint_Node *head = bigint->first; - assert(head != NULL); - Bigint_Node *tail = (Bigint_Node *) (head->next_xor_prev ^ - (uintptr_t) NULL); - if (tail == NULL) { /* last node removed */ - bigint->sign_size = 0; - bigint->first = bigint->last = (Bigint_Node *) NULL; - } else { - tail->next_xor_prev = (tail->next_xor_prev ^ (uintptr_t) head) ^ - (uintptr_t) NULL; - bigint->first = tail; - bigint->sign_size -= bigint->sign_size < 0? -1 : 1; - } - head->next_xor_prev = 0; /* NULL ^ NULL: 0 */ - return head; -} - typedef struct __attribute__ ((__packed__)) { CommonHeader; TValue mark; /* for cycle/sharing aware algorithms */ diff --git a/src/kstate.c b/src/kstate.c @@ -457,12 +457,7 @@ void klisp_close (klisp_State *K) switch(type) { case K_TBIGINT: { Bigint *bigint = (Bigint *)obj; - int size = kbigint_size(bigint); - Bigint_Node *node; - while(size--) { - node = kbigint_remove_node(bigint); - klispM_free(K, node); - } + /* XXX / TODO free array */ klispM_free(K, bigint); break; }