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

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

numbers: First attempt at converting to argvector. Start with wrappers for C_values and allocation continuation closures. Compiles cleanly, but crashes and burns (as expected)

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