source: project/release/4/numbers/trunk/numbers-c.h @ 32721

Last change on this file since 32721 was 32721, checked in by sjamaan, 5 years ago

numbers: Convert unary CPS procedures and calls to support argvector

File size: 16.6 KB
Line 
1/* numbers-c.h */
2
3/* C_cpsproc is only defined for argvector chickens */
4#ifdef C_cpsproc
5# define ARGVECTOR_CHICKEN
6#endif
7
8/* Compat helpers for extracting procedure args in a common way */
9#ifdef ARGVECTOR_CHICKEN
10# define C_kontinue2(k, r1, r2)                                         \
11  do {                                                                  \
12    C_word avk[ 4 ];                                                    \
13    avk[ 0 ] = C_SCHEME_UNDEFINED;                                      \
14    avk[ 1 ] = (k);                                                     \
15    avk[ 2 ] = (r1);                                                    \
16    avk[ 3 ] = (r2);                                                    \
17    ((C_proc)(void *)C_block_item((k),0))(4, avk); \
18  } while(0)
19/* "Allocation continuation" closures/functions; these don't receive a
20 * continuation, but they get called through an allocating function.
21 * The function that calls the allocation function needs to save the
22 * continuation in the closure, the "self" argument.
23 */
24# define CONT_BODY(s, a1) C_word s = __av[0]; C_word a1 = __av[1];
25# define CONT_PROC(name, c, s, a1)   name(C_word c, C_word *__av)
26/* cpsproc() can't easily be used in prototype and definition */
27# define CPS_PROC1(name, c, s, k, a1) name(C_word c, C_word *__av)
28# define CPS_PROC2(name, c, s, k, a1, a2) name(C_word c, C_word *__av)
29# define CPS_BODY1(c, s, k, a1) C_word s = __av[0]; C_word k = __av[1]; C_word a1 = c >= 1 ? __av[2] : 0;
30# define CPS_BODY2(c, s, k, a1, a2) C_word s = __av[0]; C_word k = __av[1]; C_word a1 = c >= 1 ? __av[2] : 0; C_word a2 = c >= 2 ? __av[3] : 0;
31# define CPS_CALL(fn, c, s, k, ...) do { C_word avk[] = {s,k,__VA_ARGS__}; fn(c, avk); } while(0)
32#else
33# define C_kontinue2(k, r1, r2) C_values(4,C_SCHEME_UNDEFINED,k,r1,r2)
34# define CONT_BODY(s, a1) /* Nothing */
35# define CONT_PROC(name, c, s, a1)   name(C_word c, C_word s, C_word a1)
36# define CPS_PROC1(name, c, s, k, a1) name(C_word c, C_word s, C_word k, C_word a1)
37# define CPS_PROC2(name, c, s, k, a1, a2) name(C_word c, C_word s, C_word k, C_word a1, C_word a2)
38# define CPS_BODY1(c, s, k, a1) /* Nothing */
39# define CPS_BODY2(c, s, k, a1, a2) /* Nothing */
40# define CPS_CALL(fn, c, s, k, ...)  fn(c, s, k, __VA_ARGS__);
41#endif
42
43#define BIG_TAG       0
44#define RAT_TAG       1
45#define COMP_TAG      2
46
47#ifdef C_SIXTY_FOUR
48# define C_HALF_WORD_SIZE           32
49# define C_hword                    int
50#else
51# define C_HALF_WORD_SIZE           16
52# define C_hword                    short
53#endif
54#define C_uhword                    unsigned C_hword
55
56#define C_SIZEOF_STRUCTURE(n)           ((n)+1) /* missing from chicken.h */
57#define C_SIZEOF_CLOSURE(n)             ((n)+1) /* missing from chicken.h */
58/* The "internal"/"external" bignum distinction should die */
59#define C_SIZEOF_INTERNAL_BIGNUM(n)     (C_SIZEOF_VECTOR((n)+1))
60#define C_internal_bignum(b)            (C_block_item(b,1))
61
62#define C_SIZEOF_BIGNUM(n)              (C_SIZEOF_INTERNAL_BIGNUM(n)+C_SIZEOF_STRUCTURE(2))
63/* This is for convenience and allows flexibility in representation */
64#define C_SIZEOF_FIX_BIGNUM             C_SIZEOF_BIGNUM(1)
65#define C_BIGNUM_DIGIT_LENGTH           C_WORD_SIZE
66#define C_BIGNUM_HALF_DIGIT_LENGTH      C_HALF_WORD_SIZE
67
68/* This defines when we'll switch from schoolbook to Karatsuba
69 * multiplication.  The smallest of the two numbers determines the
70 * switch.  It is pretty high right now because it generates a bit
71 * more garbage and GC overhead dominates the algorithmic performance
72 * gains.  If the GC is improved, this can be readjusted.
73 */
74#define C_KARATSUBA_THRESHOLD        70
75/* This defines when to switch from schoolbook to Burnikel-Ziegler
76 * division.  It creates even more garbage than Karatsuba :(
77 */
78#define C_BURNIKEL_ZIEGLER_DIFF_THRESHOLD 300
79/* This threshold is in terms of the expected string length.  It
80 * depends on division speed: if you change the above, change this too.
81 */
82#define C_RECURSIVE_TO_STRING_THRESHOLD 750
83
84#define C_BIGNUM_BITS_TO_DIGITS(n) \
85        (((n) + (C_BIGNUM_DIGIT_LENGTH - 1)) / C_BIGNUM_DIGIT_LENGTH)
86
87#define C_BIGNUM_DIGIT_LO_HALF(d)       (C_uhword)(d)
88#define C_BIGNUM_DIGIT_HI_HALF(d)       (C_uhword)((d) >> C_BIGNUM_HALF_DIGIT_LENGTH)
89#define C_BIGNUM_DIGIT_COMBINE(h,l)     ((C_uword)(h) << C_BIGNUM_HALF_DIGIT_LENGTH|(C_uhword)(l))
90
91/* Compatibility for CHICKEN < 4.9.0 */
92#ifndef C_block_header_init
93#define C_block_header_init(b, v)       C_block_header(b) = (v)
94#endif
95
96/* This should be replaced by C_header_bits(x) == C_BIGNUM_TYPE in core */
97#define C_IS_BIGNUM_TYPE(x) (C_header_bits(x) == C_STRUCTURE_TYPE && C_block_item(CHICKEN_gc_root_ref(tags), BIG_TAG) == C_block_item(x, 0))
98
99#define C_i_bignump(x)                  C_mk_bool(!C_immediatep(x) && C_IS_BIGNUM_TYPE(x))
100#define C_fitsinbignumhalfdigitp(n)     (C_BIGNUM_DIGIT_HI_HALF(n) == 0)
101#define C_bignum_negated_fitsinfixnump(b) (C_bignum_size(b) == 1 && (C_bignum_negativep(b) ? C_ufitsinfixnump(*C_bignum_digits(b)) : !(*C_bignum_digits(b) & C_INT_SIGN_BIT) && C_fitsinfixnump(-(C_word)*C_bignum_digits(b))))
102#define C_bignum_header(b)              (*(C_word *)C_data_pointer(C_internal_bignum(b)))
103#define C_bignum_digits(b)              (((C_uword *)C_data_pointer(C_internal_bignum(b)))+1)
104#define C_bignum_negativep(b)           (C_bignum_header(b) != 0)
105#define C_a_u_i_fixnum_abs(ptr, n, x)   (((x) & C_INT_SIGN_BIT) ? C_a_u_i_fixnum_negate((ptr), (n), (x)) : (x))
106#define C_u_i_fixnum_signum(x)          ((x) == C_fix(0) ? x : (((x) & C_INT_SIGN_BIT) ? C_fix(-1) : C_fix(1)))
107#define C_u_i_fixnum_negativep(x)       C_mk_bool((x) & C_INT_SIGN_BIT)
108#define C_u_i_fixnum_positivep(x)       C_mk_bool(!((x) & C_INT_SIGN_BIT) && (x) != C_fix(0))
109#define C_a_u_i_flonum_signum(ptr, n, x) (C_flonum_magnitude(x) == 0.0 ? x : ((C_flonum_magnitude(x) < 0.0) ? C_flonum(ptr, -1.0) : C_flonum(ptr, 1.0)))
110#define C_a_u_i_big_to_flo(p, n, b)     C_flonum(p, C_bignum_to_double(b))
111#define C_u_i_fixnum_length(x)          C_fix(C_ilen(((x) & C_INT_SIGN_BIT) ? ~C_unfix(x) : C_unfix(x)))
112#define C_u_i_flonum_nanp(x)            C_mk_bool(C_isnan(C_flonum_magnitude(x)))
113#define C_u_i_flonum_infinitep(x)       C_mk_bool(C_isinf(C_flonum_magnitude(x)))
114
115#define C_isfinite                      isfinite
116#define C_u_i_flonum_finitep(x)         C_mk_bool(C_isfinite(C_flonum_magnitude(x)))
117
118/* The bytes->words conversion should be killed, but that can only be
119 * done when the representation is made part of core (otherwise the GC
120 * will trip on the vector's contents not being proper Scheme objects:
121 * it skips objects marked with C_BYTEBLOCK_BIT).  We could set
122 * SPECIALBLOCK_BIT, but that would disable the number-syntax hack.
123 * So, for now we'll live with back and forth byte<->word conversion.
124 */
125#define C_bignum_size(b)                (C_bytestowords(C_header_size(C_internal_bignum(b)))-1)
126#define C_bignum_mutate_size(b, s)      (C_block_header(C_internal_bignum(b)) = (C_STRING_TYPE | C_wordstobytes((s)+1)))
127#define C_u_i_bignum_size(b)            C_fix(C_bignum_size(b))
128
129void C_not_an_integer_error(char *loc, C_word x) C_noret;
130void numbers_div_by_zero_error(char *loc) C_noret;
131
132/* XXX: When moving to core, these all need "fctexport" */
133void C_ccall C_allocate_bignum(C_word c, C_word self, C_word k, C_word size, C_word negp, C_word initp) C_noret;
134void C_ccall C_bignum_destructive_trim(C_word big);
135C_word C_ccall C_bignum_simplify(C_word big);
136void C_ccall C_u_bignum_extract_digits(C_word c, C_word self, C_word k, C_word x, C_word start, C_word end) C_noret;
137
138C_regparm double C_bignum_to_double(C_word bignum);
139C_regparm C_word C_fcall C_i_numbers_numberp(C_word x);
140C_regparm C_word C_fcall C_i_numbers_integerp(C_word x);
141C_regparm C_word C_fcall C_i_numbers_eqvp(C_word x, C_word y);
142C_regparm C_word C_fcall C_i_nanp(C_word x);
143C_regparm C_word C_fcall C_i_numbers_finitep(C_word x);
144C_regparm C_word C_fcall C_i_numbers_infinitep(C_word x);
145C_regparm C_word C_ccall C_i_numbers_zerop(C_word x);
146
147C_word C_ccall C_u_i_2_fixnum_gcd(C_word x, C_word y);
148C_word C_ccall C_a_u_i_2_flonum_gcd(C_word **p, C_word n, C_word x, C_word y);
149void C_ccall C_u_2_integer_gcd(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
150
151void C_ccall C_2_basic_plus(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
152C_regparm C_word C_fcall C_a_u_i_2_fixnum_plus(C_word **ptr, C_word n, C_word x, C_word y);
153void C_ccall C_u_2_integer_plus(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
154
155void C_ccall CPS_PROC1(C_basic_abs, c, self, k, x) C_noret;
156void C_ccall CPS_PROC1(C_u_integer_abs, c, self, k, x) C_noret;
157
158void C_ccall CPS_PROC1(C_basic_signum, c, self, k, x) C_noret;
159C_regparm C_word C_fcall C_u_i_integer_signum(C_word x);
160
161void C_ccall CPS_PROC1(C_basic_negate, c, self, k, x) C_noret;
162void C_ccall CPS_PROC1(C_u_integer_negate, c, self, k, x) C_noret;
163C_regparm C_word C_fcall C_a_u_i_fixnum_negate(C_word **ptr, C_word n, C_word x);
164
165void C_ccall C_2_basic_minus(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
166C_regparm C_word C_fcall C_a_u_i_2_fixnum_minus(C_word **ptr, C_word n, C_word x, C_word y);
167void C_ccall C_u_2_integer_minus(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
168
169void C_ccall C_2_basic_times(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
170C_regparm C_word C_fcall C_a_u_i_2_fixnum_times(C_word **ptr, C_word n, C_word x, C_word y);
171void C_ccall C_u_2_integer_times(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
172
173void C_ccall C_basic_quotient(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
174void C_ccall C_u_integer_quotient(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
175
176void C_ccall C_basic_remainder(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
177void C_ccall C_u_integer_remainder(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
178
179void C_ccall C_basic_divrem(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
180void C_ccall C_u_integer_divrem(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
181
182void C_ccall C_numbers_nequalp(C_word c, C_word self, C_word k, ...) C_noret;
183C_regparm C_word C_fcall C_i_2_basic_equalp(C_word x, C_word y);
184C_word C_ccall C_u_i_2_integer_equalp(C_word x, C_word y);
185void C_ccall C_numbers_lessp(C_word c, C_word self, C_word k, ...) C_noret;
186C_regparm C_word C_fcall C_i_2_basic_lessp(C_word x, C_word y);
187C_word C_ccall C_u_i_2_integer_lessp(C_word x, C_word y);
188void C_ccall C_numbers_less_or_equalp(C_word c, C_word self, C_word k, ...) C_noret;
189C_regparm C_word C_fcall C_i_2_basic_less_or_equalp(C_word x, C_word y);
190C_word C_ccall C_u_i_2_integer_or_equal_p(C_word x, C_word y);
191void C_ccall C_numbers_greaterp(C_word c, C_word self, C_word k, ...) C_noret;
192C_regparm C_word C_fcall C_i_2_basic_greaterp(C_word x, C_word y);
193C_word C_ccall C_u_i_2_integer_greaterp(C_word x, C_word y);
194void C_ccall C_numbers_greater_or_equal_p(C_word c, C_word self, C_word k, ...) C_noret;
195C_regparm C_word C_fcall C_i_2_basic_greater_or_equalp(C_word x, C_word y);
196C_word C_ccall C_u_i_2_integer_or_equalp(C_word x, C_word y);
197
198C_word C_u_i_bignum_cmp(C_word x, C_word y);
199
200/** TODO: rename to C_i_evenp/C_i_oddp, or is this fine? */
201C_regparm C_word C_fcall C_i_basic_evenp(C_word x);
202C_regparm C_word C_fcall C_u_i_integer_evenp(C_word x);
203C_regparm C_word C_fcall C_i_basic_oddp(C_word x);
204C_regparm C_word C_fcall C_u_i_integer_oddp(C_word x);
205C_regparm C_word C_fcall C_i_basic_positivep(C_word x);
206C_regparm C_word C_fcall C_u_i_integer_positivep(C_word x);
207C_regparm C_word C_fcall C_i_basic_negativep(C_word x);
208C_regparm C_word C_fcall C_u_i_integer_negativep(C_word x);
209
210C_regparm C_word C_ccall C_u_i_integer_randomize(C_word seed);
211void C_ccall CPS_PROC1(C_u_integer_random, c, self, k, max) C_noret;
212
213void C_ccall C_digits_to_integer(C_word c, C_word self, C_word k, C_word n, C_word start, C_word end, C_word radix, C_word negp) C_noret;
214void C_ccall C_basic_number_to_string(C_word c, C_word closure, C_word k, C_word num, ...) C_noret;
215void C_ccall C_u_fixnum_to_string(C_word c, C_word self, C_word k, C_word num, C_word radix) C_noret;
216void C_ccall C_u_flonum_to_string(C_word c, C_word self, C_word k, C_word num, C_word radix) C_noret;
217void C_ccall C_u_integer_to_string(C_word c, C_word self, C_word k, C_word num, C_word radix) C_noret;
218void C_ccall C_u_fixnum_to_string(C_word c, C_word self, C_word k, C_word num, C_word radix) C_noret;
219void C_ccall CPS_PROC1(C_u_flo_to_int, c, self, k, x) C_noret;
220C_word C_ccall C_u_i_integer_bit_setp(C_word n, C_word i);
221C_word C_ccall C_u_i_integer_length(C_word x);
222
223void C_ccall C_u_integer_shift(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
224void C_ccall C_u_2_integer_bitwise_and(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
225void C_ccall C_u_2_integer_bitwise_ior(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
226void C_ccall C_u_2_integer_bitwise_xor(C_word c, C_word self, C_word k, C_word x, C_word y) C_noret;
227
228/* Silly but in some cases needed */
229C_inline C_word C_bignum0(C_word **ptr)
230{
231  C_word *p = *ptr, p0 = (C_word)p;
232
233  C_word tagvec = CHICKEN_gc_root_ref(tags);
234
235  /* Not using C_a_i_vector4, to make it easier to rewrite later */
236  *(p++) = C_STRING_TYPE | C_wordstobytes(1);
237  *(p++) = 0; /* zero is always positive */
238  *ptr = p;
239
240  return C_structure(ptr, 2, C_block_item(tagvec, BIG_TAG), p0);
241}
242
243C_inline C_word C_bignum1(C_word **ptr, int negp, C_uword d1)
244{
245  C_word *p = *ptr, p0 = (C_word)p;
246
247  /* TODO: Get rid of structure wrapper and tag vector. */
248  C_word tagvec = CHICKEN_gc_root_ref(tags);
249
250  /* Not using C_a_i_vector2, to make it easier to rewrite later */
251  *(p++) = C_STRING_TYPE | C_wordstobytes(2);
252  *(p++) = negp;
253  *(p++) = d1;
254  *ptr = p;
255
256  return C_a_i_record2(ptr, 2, C_block_item(tagvec, BIG_TAG), p0);
257}
258
259/* Here d1, d2, ... are low to high (ie, little endian)! */
260C_inline C_word C_bignum2(C_word **ptr, int negp, C_uword d1, C_uword d2)
261{
262  C_word *p = *ptr, p0 = (C_word)p;
263
264  C_word tagvec = CHICKEN_gc_root_ref(tags);
265
266  /* Not using C_a_i_vector3, to make it easier to rewrite later */
267  *(p++) = C_STRING_TYPE | C_wordstobytes(3);
268  *(p++) = negp;
269  *(p++) = d1;
270  *(p++) = d2;
271  *ptr = p;
272
273  return C_a_i_record2(ptr, 2, C_block_item(tagvec, BIG_TAG), p0);
274}
275
276/* TODO: Is this correctly named?  Shouldn't it accept an argcount? */
277C_inline C_word C_a_u_i_fix_to_big(C_word **ptr, C_word x)
278{
279  x = C_unfix(x);
280  if (x < 0)
281    return C_bignum1(ptr, 1, -x);
282  else if (x == 0)
283    return C_bignum0(ptr);
284  else
285    return C_bignum1(ptr, 0, x);
286}
287
288/* XXX: Naming convention is inconsistent!  Core has C_fixnum_divide()
289 * but also C_a_i_flonum_quotient_checked()
290 */
291C_inline C_word C_a_u_i_fixnum_quotient_checked(C_word **ptr, int c, C_word x, C_word y)
292{
293  if (y == C_fix(0)) {
294    numbers_div_by_zero_error("fx/");
295  } else if (x == C_fix(C_MOST_NEGATIVE_FIXNUM) && y == C_fix(-1)) {
296    return C_bignum1(ptr, 0, -C_MOST_NEGATIVE_FIXNUM); /* Special case */
297  } else {
298    return C_u_fixnum_divide(x, y); /* Inconsistent, too: missing _i_ */
299  }
300}
301
302C_inline C_word C_u_i_fixnum_remainder_checked(C_word x, C_word y)
303{
304  if (y == C_fix(0)) {
305    numbers_div_by_zero_error("remainder");
306  } else {
307    x = C_unfix(x);
308    y = C_unfix(y);
309    return C_fix(x - ((x / y) * y));
310  }
311}
312
313/* Workaround for CHICKENs < 4.9.0, which contain broken fpintegerp */
314C_inline C_word C_u_i_fpintegerp_fixed(C_word x)
315{
316  double dummy, val;
317
318  val = C_flonum_magnitude(x);
319
320  if(C_isnan(val) || C_isinf(val)) return C_SCHEME_FALSE;
321
322  return C_mk_bool(C_modf(val, &dummy) == 0.0);
323}
324
325
326/* More weirdness: the other flonum_quotient macros and inline functions
327 * do not compute the quotient but the "plain" division!
328 */
329C_inline C_word
330C_a_i_flonum_actual_quotient_checked(C_word **ptr, int c, C_word x, C_word y)
331{
332  double dy = C_flonum_magnitude(y), r;
333
334  if(dy == 0.0) {
335    numbers_div_by_zero_error("quotient");
336  } else if (!C_truep(C_u_i_fpintegerp_fixed(x))) {
337    C_not_an_integer_error("quotient", x);
338  } else if (!C_truep(C_u_i_fpintegerp_fixed(y))) {
339    C_not_an_integer_error("quotient", y);
340  } else {
341    modf(C_flonum_magnitude(x) / dy, &r);
342    return C_flonum(ptr, r);
343  }
344}
345
346C_inline C_word
347C_a_i_flonum_remainder_checked(C_word **ptr, int c, C_word x, C_word y)
348{
349  double dx = C_flonum_magnitude(x),
350         dy = C_flonum_magnitude(y), r;
351
352  if(dy == 0.0) {
353    numbers_div_by_zero_error("remainder");
354  } else if (!C_truep(C_u_i_fpintegerp_fixed(x))) {
355    C_not_an_integer_error("remainder", x);
356  } else if (!C_truep(C_u_i_fpintegerp_fixed(y))) {
357    C_not_an_integer_error("remainder", y);
358  } else {
359    modf(dx / dy, &r);
360    return C_flonum(ptr, dx - r * dy);
361  }
362}
363
364/*
365 * From Hacker's Delight by Henry S. Warren
366 * based on a modified nlz() from section 5-3 (fig. 5-7)
367 */
368C_inline int C_ilen(C_uword x)
369{
370  C_uword y;
371  C_word n = 0;
372
373#ifdef C_SIXTY_FOUR
374  y = x >> 32; if (y != 0) { n += 32; x = y; }
375#endif
376  y = x >> 16; if (y != 0) { n += 16; x = y; }
377  y = x >>  8; if (y != 0) { n +=  8; x = y; }
378  y = x >>  4; if (y != 0) { n +=  4; x = y; }
379  y = x >>  2; if (y != 0) { n +=  2; x = y; }
380  y = x >>  1; if (y != 0) return n + 2;
381  return n + x;
382}
Note: See TracBrowser for help on using the repository browser.