commit e5af907da4402212f37151c50fe61f8d13ab615f
parent 33b87dafccd559d25f27b393fde1b434701e88cd
Author: Andres Navarro <canavarro82@gmail.com>
Date: Sat, 9 Apr 2011 23:33:37 -0300
Added printing of bigints (and memory freeing on exit).
Diffstat:
5 files changed, 185 insertions(+), 3 deletions(-)
diff --git a/src/kinteger.c b/src/kinteger.c
@@ -7,6 +7,7 @@
#include <stdbool.h>
#include <stdint.h>
#include <inttypes.h>
+#include <math.h>
#include "kinteger.h"
#include "kobject.h"
@@ -18,6 +19,8 @@
#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);
@@ -54,6 +57,25 @@ TValue kbigint_new(klisp_State *K, bool sign, uint32_t digit)
return gc2bigint(new_bigint);
}
+/* 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;
+}
+
/* 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 */
@@ -82,9 +104,88 @@ void kbigint_add_digit(klisp_State *K, TValue tv_bigint, int32_t base,
}
}
+/* 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;
+}
+
+/* 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;
+}
+
+bool kbigint_negativep(TValue tv_bigint)
+{
+ return kbigint_negp(tv2bigint(tv_bigint));
+}
+
+bool kbigint_positivep(TValue tv_bigint)
+{
+ return kbigint_posp(tv2bigint(tv_bigint));
+}
+
/* Mutate the bigint to have the opposite sign, used in read */
void kbigint_invert_sign(TValue tv_bigint)
{
Bigint *bigint = tv2bigint(tv_bigint);
bigint->sign_size = -bigint->sign_size;
}
+
+/* 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);
+}
diff --git a/src/kinteger.h b/src/kinteger.h
@@ -18,6 +18,8 @@
/* 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);
/* Create a stack allocated bigints from a fixint,
useful for mixed operations, relatively light weight compared
@@ -34,11 +36,25 @@ TValue kbigint_new(klisp_State *K, bool sign, uint32_t digit);
(KUNIQUE_NAME(bigint)).sign_size = (KUNIQUE_NAME(i)) < 0? -1 : 1; \
Bigint *name = &(KUNIQUE_NAME(bigint));
-/* This is used by the reader to destructively add digits to a number */
+/* 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,
int32_t digit);
-/* Mutate the bigint to have the opposite sign, used in read */
+/* 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);
+
+/* 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);
+
+bool kbigint_negativep(TValue tv_bigint);
+bool kbigint_positivep(TValue tv_bigint);
+/* Mutate the bigint to have the opposite sign, used in read & write */
void kbigint_invert_sign(TValue tv_bigint);
+/* 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);
+
#endif
diff --git a/src/kobject.h b/src/kobject.h
@@ -285,7 +285,7 @@ typedef struct __attribute__ ((__packed__)) {
/* macros to access size/sign */
#define kbigint_sign(b_) ((b_)->sign_size < 0)
-#define kbigint_negp(b_) (kgigint_sign(b_))
+#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;})
@@ -354,6 +354,27 @@ inline void kbigint_add_node(Bigint *bigint, Bigint_Node *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
@@ -455,6 +455,17 @@ void klisp_close (klisp_State *K)
int type = gch_get_type(obj);
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);
+ }
+ klispM_free(K, bigint);
+ break;
+ }
case K_TPAIR:
klispM_free(K, (Pair *)obj);
break;
diff --git a/src/kwrite.c b/src/kwrite.c
@@ -11,6 +11,7 @@
#include "kwrite.h"
#include "kobject.h"
+#include "kinteger.h"
#include "kpair.h"
#include "kstring.h"
#include "ksymbol.h"
@@ -37,6 +38,35 @@ void kwrite_error(klisp_State *K, char *msg)
/* TODO: check for return codes and throw error if necessary */
+void kw_print_bigint(klisp_State *K, TValue bigint)
+{
+ /* XXX: calculate appropiate size & malloc string,
+ leave space for sign */
+ int32_t size = kbigint_print_size(bigint, 10);
+ TValue buf_str = kstring_new_g(K, size);
+ /* write backwards so we can use printf later */
+ char *buf = kstring_buf(buf_str) + size - 1;
+ /* GC: root copy */
+ TValue copy = kbigint_copy(K, bigint);
+ /* must work with positive bigint to get the digits */
+ if (kbigint_negativep(bigint))
+ kbigint_invert_sign(copy);
+
+ 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-- = '-';
+
+ kw_printf(K, "%s", buf+1);
+ /* MAYBE: we could free the copy & string instead of letting the
+ gc do it */
+}
+
/*
** Helper for printing strings (correcly escapes backslashes and
** double quotes & prints embedded '\0's). It includes the surrounding
@@ -166,6 +196,9 @@ void kwrite_simple(klisp_State *K, TValue obj)
case K_TFIXINT:
kw_printf(K, "%" PRId32, ivalue(obj));
break;
+ case K_TBIGINT:
+ kw_print_bigint(K, obj);
+ break;
case K_TNIL:
kw_printf(K, "()");
break;
