-
Notifications
You must be signed in to change notification settings - Fork 0
/
bignum.h
247 lines (225 loc) · 7.16 KB
/
bignum.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
#ifndef INTERNAL_BIGNUM_H /*-*-C-*-vi:se ft=c:*/
#define INTERNAL_BIGNUM_H
/**
* @file
* @author Ruby developers <ruby-core@ruby-lang.org>
* @copyright This file is a part of the programming language Ruby.
* Permission is hereby granted, to either redistribute and/or
* modify this file, provided that the conditions mentioned in the
* file COPYING are met. Consult the file for details.
* @brief Internal header for Bignums.
*/
#include "ruby/internal/config.h" /* for HAVE_LIBGMP */
#include <stddef.h> /* for size_t */
#ifdef HAVE_SYS_TYPES_H
# include <sys/types.h> /* for ssize_t (note: on Windows ssize_t is */
#endif /* `#define`d in ruby/config.h) */
#include "ruby/internal/stdbool.h" /* for bool */
#include "ruby/ruby.h" /* for struct RBasic */
#ifndef BDIGIT
# if SIZEOF_INT*2 <= SIZEOF_LONG_LONG
# define BDIGIT unsigned int
# define SIZEOF_BDIGIT SIZEOF_INT
# define BDIGIT_DBL unsigned LONG_LONG
# define BDIGIT_DBL_SIGNED LONG_LONG
# define PRI_BDIGIT_PREFIX ""
# define PRI_BDIGIT_DBL_PREFIX PRI_LL_PREFIX
# elif SIZEOF_INT*2 <= SIZEOF_LONG
# define BDIGIT unsigned int
# define SIZEOF_BDIGIT SIZEOF_INT
# define BDIGIT_DBL unsigned long
# define BDIGIT_DBL_SIGNED long
# define PRI_BDIGIT_PREFIX ""
# define PRI_BDIGIT_DBL_PREFIX "l"
# elif SIZEOF_SHORT*2 <= SIZEOF_LONG
# define BDIGIT unsigned short
# define SIZEOF_BDIGIT SIZEOF_SHORT
# define BDIGIT_DBL unsigned long
# define BDIGIT_DBL_SIGNED long
# define PRI_BDIGIT_PREFIX "h"
# define PRI_BDIGIT_DBL_PREFIX "l"
# else
# define BDIGIT unsigned short
# define SIZEOF_BDIGIT (SIZEOF_LONG/2)
# define SIZEOF_ACTUAL_BDIGIT SIZEOF_LONG
# define BDIGIT_DBL unsigned long
# define BDIGIT_DBL_SIGNED long
# define PRI_BDIGIT_PREFIX "h"
# define PRI_BDIGIT_DBL_PREFIX "l"
# endif
#endif
#ifndef SIZEOF_ACTUAL_BDIGIT
# define SIZEOF_ACTUAL_BDIGIT SIZEOF_BDIGIT
#endif
#ifdef PRI_BDIGIT_PREFIX
# define PRIdBDIGIT PRI_BDIGIT_PREFIX"d"
# define PRIiBDIGIT PRI_BDIGIT_PREFIX"i"
# define PRIoBDIGIT PRI_BDIGIT_PREFIX"o"
# define PRIuBDIGIT PRI_BDIGIT_PREFIX"u"
# define PRIxBDIGIT PRI_BDIGIT_PREFIX"x"
# define PRIXBDIGIT PRI_BDIGIT_PREFIX"X"
#endif
#ifdef PRI_BDIGIT_DBL_PREFIX
# define PRIdBDIGIT_DBL PRI_BDIGIT_DBL_PREFIX"d"
# define PRIiBDIGIT_DBL PRI_BDIGIT_DBL_PREFIX"i"
# define PRIoBDIGIT_DBL PRI_BDIGIT_DBL_PREFIX"o"
# define PRIuBDIGIT_DBL PRI_BDIGIT_DBL_PREFIX"u"
# define PRIxBDIGIT_DBL PRI_BDIGIT_DBL_PREFIX"x"
# define PRIXBDIGIT_DBL PRI_BDIGIT_DBL_PREFIX"X"
#endif
#define RBIGNUM(obj) ((struct RBignum *)(obj))
#define BIGNUM_SIGN_BIT FL_USER1
#define BIGNUM_EMBED_FLAG ((VALUE)FL_USER2)
#define BIGNUM_EMBED_LEN_NUMBITS 3
#define BIGNUM_EMBED_LEN_MASK \
(~(~(VALUE)0U << BIGNUM_EMBED_LEN_NUMBITS) << BIGNUM_EMBED_LEN_SHIFT)
#define BIGNUM_EMBED_LEN_SHIFT \
(FL_USHIFT+3) /* bit offset of BIGNUM_EMBED_LEN_MASK */
#ifndef BIGNUM_EMBED_LEN_MAX
# if (SIZEOF_VALUE*RVALUE_EMBED_LEN_MAX/SIZEOF_ACTUAL_BDIGIT) < (1 << BIGNUM_EMBED_LEN_NUMBITS)-1
# define BIGNUM_EMBED_LEN_MAX (SIZEOF_VALUE*RVALUE_EMBED_LEN_MAX/SIZEOF_ACTUAL_BDIGIT)
# else
# define BIGNUM_EMBED_LEN_MAX ((1 << BIGNUM_EMBED_LEN_NUMBITS)-1)
# endif
#endif
enum rb_int_parse_flags {
RB_INT_PARSE_SIGN = 0x01,
RB_INT_PARSE_UNDERSCORE = 0x02,
RB_INT_PARSE_PREFIX = 0x04,
RB_INT_PARSE_ALL = 0x07,
RB_INT_PARSE_DEFAULT = 0x07,
};
struct RBignum {
struct RBasic basic;
union {
struct {
size_t len;
BDIGIT *digits;
} heap;
BDIGIT ary[BIGNUM_EMBED_LEN_MAX];
} as;
};
/* bignum.c */
extern const char ruby_digitmap[];
double rb_big_fdiv_double(VALUE x, VALUE y);
VALUE rb_big_uminus(VALUE x);
VALUE rb_big_hash(VALUE);
VALUE rb_big_odd_p(VALUE);
VALUE rb_big_even_p(VALUE);
size_t rb_big_size(VALUE);
VALUE rb_integer_float_cmp(VALUE x, VALUE y);
VALUE rb_integer_float_eq(VALUE x, VALUE y);
VALUE rb_str_convert_to_inum(VALUE str, int base, int badcheck, int raise_exception);
VALUE rb_big_comp(VALUE x);
VALUE rb_big_aref(VALUE x, VALUE y);
VALUE rb_big_abs(VALUE x);
VALUE rb_big_size_m(VALUE big);
VALUE rb_big_bit_length(VALUE big);
VALUE rb_big_remainder(VALUE x, VALUE y);
VALUE rb_big_gt(VALUE x, VALUE y);
VALUE rb_big_ge(VALUE x, VALUE y);
VALUE rb_big_lt(VALUE x, VALUE y);
VALUE rb_big_le(VALUE x, VALUE y);
VALUE rb_int_powm(int const argc, VALUE * const argv, VALUE const num);
VALUE rb_big_isqrt(VALUE n);
static inline bool BIGNUM_SIGN(VALUE b);
static inline bool BIGNUM_POSITIVE_P(VALUE b);
static inline bool BIGNUM_NEGATIVE_P(VALUE b);
static inline void BIGNUM_SET_SIGN(VALUE b, bool sign);
static inline void BIGNUM_NEGATE(VALUE b);
static inline size_t BIGNUM_LEN(VALUE b);
static inline BDIGIT *BIGNUM_DIGITS(VALUE b);
static inline int BIGNUM_LENINT(VALUE b);
static inline bool BIGNUM_EMBED_P(VALUE b);
RUBY_SYMBOL_EXPORT_BEGIN
/* bignum.c (export) */
VALUE rb_big_mul_normal(VALUE x, VALUE y);
VALUE rb_big_mul_balance(VALUE x, VALUE y);
VALUE rb_big_mul_karatsuba(VALUE x, VALUE y);
VALUE rb_big_mul_toom3(VALUE x, VALUE y);
VALUE rb_big_sq_fast(VALUE x);
VALUE rb_big_divrem_normal(VALUE x, VALUE y);
VALUE rb_big2str_poweroftwo(VALUE x, int base);
VALUE rb_big2str_generic(VALUE x, int base);
VALUE rb_str2big_poweroftwo(VALUE arg, int base, int badcheck);
VALUE rb_str2big_normal(VALUE arg, int base, int badcheck);
VALUE rb_str2big_karatsuba(VALUE arg, int base, int badcheck);
#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H)
VALUE rb_big_mul_gmp(VALUE x, VALUE y);
VALUE rb_big_divrem_gmp(VALUE x, VALUE y);
VALUE rb_big2str_gmp(VALUE x, int base);
VALUE rb_str2big_gmp(VALUE arg, int base, int badcheck);
#endif
VALUE rb_int_parse_cstr(const char *str, ssize_t len, char **endp, size_t *ndigits, int base, int flags);
RUBY_SYMBOL_EXPORT_END
MJIT_SYMBOL_EXPORT_BEGIN
#if defined(HAVE_INT128_T)
VALUE rb_int128t2big(int128_t n);
#endif
MJIT_SYMBOL_EXPORT_END
/* sign: positive:1, negative:0 */
static inline bool
BIGNUM_SIGN(VALUE b)
{
return FL_TEST_RAW(b, BIGNUM_SIGN_BIT);
}
static inline bool
BIGNUM_POSITIVE_P(VALUE b)
{
return BIGNUM_SIGN(b);
}
static inline bool
BIGNUM_NEGATIVE_P(VALUE b)
{
return ! BIGNUM_POSITIVE_P(b);
}
static inline void
BIGNUM_SET_SIGN(VALUE b, bool sign)
{
if (sign) {
FL_SET_RAW(b, BIGNUM_SIGN_BIT);
}
else {
FL_UNSET_RAW(b, BIGNUM_SIGN_BIT);
}
}
static inline void
BIGNUM_NEGATE(VALUE b)
{
FL_REVERSE_RAW(b, BIGNUM_SIGN_BIT);
}
static inline size_t
BIGNUM_LEN(VALUE b)
{
if (! BIGNUM_EMBED_P(b)) {
return RBIGNUM(b)->as.heap.len;
}
else {
size_t ret = RBASIC(b)->flags;
ret &= BIGNUM_EMBED_LEN_MASK;
ret >>= BIGNUM_EMBED_LEN_SHIFT;
return ret;
}
}
static inline int
BIGNUM_LENINT(VALUE b)
{
return rb_long2int(BIGNUM_LEN(b));
}
/* LSB:BIGNUM_DIGITS(b)[0], MSB:BIGNUM_DIGITS(b)[BIGNUM_LEN(b)-1] */
static inline BDIGIT *
BIGNUM_DIGITS(VALUE b)
{
if (BIGNUM_EMBED_P(b)) {
return RBIGNUM(b)->as.ary;
}
else {
return RBIGNUM(b)->as.heap.digits;
}
}
static inline bool
BIGNUM_EMBED_P(VALUE b)
{
return FL_TEST_RAW(b, BIGNUM_EMBED_FLAG);
}
#endif /* INTERNAL_BIGNUM_H */