1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13: #include "ruby/ruby.h"
14:
15: #include <math.h>
16: #include <float.h>
17: #include <ctype.h>
18: #ifdef HAVE_IEEEFP_H
19: #include <ieeefp.h>
20: #endif
21:
22: VALUE rb_cBignum;
23:
24: #if defined __MINGW32__
25: #define USHORT _USHORT
26: #endif
27:
28: #define BDIGITS(x) (RBIGNUM_DIGITS(x))
29: #define BITSPERDIG (SIZEOF_BDIGITS*CHAR_BIT)
30: #define BIGRAD ((BDIGIT_DBL)1 << BITSPERDIG)
31: #define DIGSPERLONG ((unsigned int)(SIZEOF_LONG/SIZEOF_BDIGITS))
32: #if HAVE_LONG_LONG
33: # define DIGSPERLL ((unsigned int)(SIZEOF_LONG_LONG/SIZEOF_BDIGITS))
34: #endif
35: #define BIGUP(x) ((BDIGIT_DBL)(x) << BITSPERDIG)
36: #define BIGDN(x) RSHIFT(x,BITSPERDIG)
37: #define BIGLO(x) ((BDIGIT)((x) & (BIGRAD-1)))
38: #define BDIGMAX ((BDIGIT)-1)
39:
40: #define BIGZEROP(x) (RBIGNUM_LEN(x) == 0 || (RBIGNUM_LEN(x) == 1 && BDIGITS(x)[0] == 0))
41:
42: #define RBIGNUM_SET_LEN(b,l) \
43: ((RBASIC(b)->flags & RBIGNUM_EMBED_FLAG) ? \
44: (RBASIC(b)->flags = (RBASIC(b)->flags & ~RBIGNUM_EMBED_LEN_MASK) | \
45: ((l) << RBIGNUM_EMBED_LEN_SHIFT)) : \
46: (RBIGNUM(b)->as.heap.len = (l)))
47:
48: static void
49: rb_big_realloc(VALUE big, long len)
50: {
51: BDIGIT *ds;
52: if (RBASIC(big)->flags & RBIGNUM_EMBED_FLAG) {
53: if (RBIGNUM_EMBED_LEN_MAX < len) {
54: ds = ALLOC_N(BDIGIT, len);
55: MEMCPY(ds, RBIGNUM(big)->as.ary, BDIGIT, RBIGNUM_EMBED_LEN_MAX);
56: RBIGNUM(big)->as.heap.len = RBIGNUM_LEN(big);
57: RBIGNUM(big)->as.heap.digits = ds;
58: RBASIC(big)->flags &= ~RBIGNUM_EMBED_FLAG;
59: }
60: }
61: else {
62: if (len <= RBIGNUM_EMBED_LEN_MAX) {
63: ds = RBIGNUM(big)->as.heap.digits;
64: RBASIC(big)->flags |= RBIGNUM_EMBED_FLAG;
65: RBIGNUM_SET_LEN(big, len);
66: if (ds) {
67: MEMCPY(RBIGNUM(big)->as.ary, ds, BDIGIT, len);
68: free(ds);
69: }
70: }
71: else {
72: if (RBIGNUM_LEN(big) == 0) {
73: RBIGNUM(big)->as.heap.digits = ALLOC_N(BDIGIT, len);
74: }
75: else {
76: REALLOC_N(RBIGNUM(big)->as.heap.digits, BDIGIT, len);
77: }
78: }
79: }
80: }
81:
82: void
83: rb_big_resize(VALUE big, long len)
84: {
85: rb_big_realloc(big, len);
86: RBIGNUM_SET_LEN(big, len);
87: }
88:
89: static VALUE
90: bignew_1(VALUE klass, long len, int sign)
91: {
92: NEWOBJ(big, struct RBignum);
93: OBJSETUP(big, klass, T_BIGNUM);
94: RBIGNUM_SET_SIGN(big, sign?1:0);
95: if (len <= RBIGNUM_EMBED_LEN_MAX) {
96: RBASIC(big)->flags |= RBIGNUM_EMBED_FLAG;
97: RBIGNUM_SET_LEN(big, len);
98: }
99: else {
100: rb_big_resize((VALUE)big, len);
101: }
102:
103: return (VALUE)big;
104: }
105:
106: #define bignew(len,sign) bignew_1(rb_cBignum,len,sign)
107:
108: VALUE
109: rb_big_clone(VALUE x)
110: {
111: VALUE z = bignew_1(CLASS_OF(x), RBIGNUM_LEN(x), RBIGNUM_SIGN(x));
112:
113: MEMCPY(BDIGITS(z), BDIGITS(x), BDIGIT, RBIGNUM_LEN(x));
114: return z;
115: }
116:
117:
118: static void
119: get2comp(VALUE x)
120: {
121: long i = RBIGNUM_LEN(x);
122: BDIGIT *ds = BDIGITS(x);
123: BDIGIT_DBL num;
124:
125: if (!i) return;
126: while (i--) ds[i] = ~ds[i];
127: i = 0; num = 1;
128: do {
129: num += ds[i];
130: ds[i++] = BIGLO(num);
131: num = BIGDN(num);
132: } while (i < RBIGNUM_LEN(x));
133: if (num != 0) {
134: rb_big_resize(x, RBIGNUM_LEN(x)+1);
135: ds = BDIGITS(x);
136: ds[RBIGNUM_LEN(x)-1] = 1;
137: }
138: }
139:
140: void
141: rb_big_2comp(VALUE x)
142: {
143: get2comp(x);
144: }
145:
146: static VALUE
147: bigtrunc(VALUE x)
148: {
149: long len = RBIGNUM_LEN(x);
150: BDIGIT *ds = BDIGITS(x);
151:
152: if (len == 0) return x;
153: while (--len && !ds[len]);
154: rb_big_resize(x, len+1);
155: return x;
156: }
157:
158: static VALUE
159: bigfixize(VALUE x)
160: {
161: long len = RBIGNUM_LEN(x);
162: BDIGIT *ds = BDIGITS(x);
163:
164: if (len*SIZEOF_BDIGITS <= sizeof(long)) {
165: long num = 0;
166: while (len--) {
167: num = BIGUP(num) + ds[len];
168: }
169: if (num >= 0) {
170: if (RBIGNUM_SIGN(x)) {
171: if (POSFIXABLE(num)) return LONG2FIX(num);
172: }
173: else {
174: if (NEGFIXABLE(-(long)num)) return LONG2FIX(-(long)num);
175: }
176: }
177: }
178: return x;
179: }
180:
181: static VALUE
182: bignorm(VALUE x)
183: {
184: if (!FIXNUM_P(x) && TYPE(x) == T_BIGNUM) {
185: x = bigfixize(bigtrunc(x));
186: }
187: return x;
188: }
189:
190: VALUE
191: rb_big_norm(VALUE x)
192: {
193: return bignorm(x);
194: }
195:
196: VALUE
197: rb_uint2big(VALUE n)
198: {
199: BDIGIT_DBL num = n;
200: long i = 0;
201: BDIGIT *digits;
202: VALUE big;
203:
204: big = bignew(DIGSPERLONG, 1);
205: digits = BDIGITS(big);
206: while (i < DIGSPERLONG) {
207: digits[i++] = BIGLO(num);
208: num = BIGDN(num);
209: }
210:
211: i = DIGSPERLONG;
212: while (--i && !digits[i]) ;
213: RBIGNUM_SET_LEN(big, i+1);
214: return big;
215: }
216:
217: VALUE
218: rb_int2big(SIGNED_VALUE n)
219: {
220: long neg = 0;
221: VALUE big;
222:
223: if (n < 0) {
224: n = -n;
225: neg = 1;
226: }
227: big = rb_uint2big(n);
228: if (neg) {
229: RBIGNUM_SET_SIGN(big, 0);
230: }
231: return big;
232: }
233:
234: VALUE
235: rb_uint2inum(VALUE n)
236: {
237: if (POSFIXABLE(n)) return LONG2FIX(n);
238: return rb_uint2big(n);
239: }
240:
241: VALUE
242: rb_int2inum(SIGNED_VALUE n)
243: {
244: if (FIXABLE(n)) return LONG2FIX(n);
245: return rb_int2big(n);
246: }
247:
248: #ifdef HAVE_LONG_LONG
249:
250: void
251: rb_quad_pack(char *buf, VALUE val)
252: {
253: LONG_LONG q;
254:
255: val = rb_to_int(val);
256: if (FIXNUM_P(val)) {
257: q = FIX2LONG(val);
258: }
259: else {
260: long len = RBIGNUM_LEN(val);
261: BDIGIT *ds;
262:
263: if (len > SIZEOF_LONG_LONG/SIZEOF_BDIGITS) {
264: len = SIZEOF_LONG_LONG/SIZEOF_BDIGITS;
265: }
266: ds = BDIGITS(val);
267: q = 0;
268: while (len--) {
269: q = BIGUP(q);
270: q += ds[len];
271: }
272: if (!RBIGNUM_SIGN(val)) q = -q;
273: }
274: memcpy(buf, (char*)&q, SIZEOF_LONG_LONG);
275: }
276:
277: VALUE
278: rb_quad_unpack(const char *buf, int sign)
279: {
280: unsigned LONG_LONG q;
281: long neg = 0;
282: long i;
283: BDIGIT *digits;
284: VALUE big;
285:
286: memcpy(&q, buf, SIZEOF_LONG_LONG);
287: if (sign) {
288: if (FIXABLE((LONG_LONG)q)) return LONG2FIX((LONG_LONG)q);
289: if ((LONG_LONG)q < 0) {
290: q = -(LONG_LONG)q;
291: neg = 1;
292: }
293: }
294: else {
295: if (POSFIXABLE(q)) return LONG2FIX(q);
296: }
297:
298: i = 0;
299: big = bignew(DIGSPERLL, 1);
300: digits = BDIGITS(big);
301: while (i < DIGSPERLL) {
302: digits[i++] = BIGLO(q);
303: q = BIGDN(q);
304: }
305:
306: i = DIGSPERLL;
307: while (i-- && !digits[i]) ;
308: RBIGNUM_SET_LEN(big, i+1);
309:
310: if (neg) {
311: RBIGNUM_SET_SIGN(big, 0);
312: }
313: return bignorm(big);
314: }
315:
316: #else
317:
318: #define QUAD_SIZE 8
319:
320: void
321: rb_quad_pack(char *buf, VALUE val)
322: {
323: long len;
324:
325: memset(buf, 0, QUAD_SIZE);
326: val = rb_to_int(val);
327: if (FIXNUM_P(val)) {
328: val = rb_int2big(FIX2LONG(val));
329: }
330: len = RBIGNUM_LEN(val) * SIZEOF_BDIGITS;
331: if (len > QUAD_SIZE) {
332: rb_raise(rb_eRangeError, "bignum too big to convert into `quad int'");
333: }
334: memcpy(buf, (char*)BDIGITS(val), len);
335: if (!RBIGNUM_SIGN(val)) {
336: len = QUAD_SIZE;
337: while (len--) {
338: *buf = ~*buf;
339: buf++;
340: }
341: }
342: }
343:
344: #define BNEG(b) (RSHIFT(((BDIGIT*)b)[QUAD_SIZE/SIZEOF_BDIGITS-1],BITSPERDIG-1) != 0)
345:
346: VALUE
347: rb_quad_unpack(const char *buf, int sign)
348: {
349: VALUE big = bignew(QUAD_SIZE/SIZEOF_BDIGITS, 1);
350:
351: memcpy((char*)BDIGITS(big), buf, QUAD_SIZE);
352: if (sign && BNEG(buf)) {
353: long len = QUAD_SIZE;
354: char *tmp = (char*)BDIGITS(big);
355:
356: RBIGNUM_SET_SIGN(big, 0);
357: while (len--) {
358: *tmp = ~*tmp;
359: tmp++;
360: }
361: }
362:
363: return bignorm(big);
364: }
365:
366: #endif
367:
368: VALUE
369: rb_cstr_to_inum(const char *str, int base, int badcheck)
370: {
371: const char *s = str;
372: char *end;
373: char sign = 1, nondigit = 0;
374: int c;
375: BDIGIT_DBL num;
376: long len, blen = 1;
377: long i;
378: VALUE z;
379: BDIGIT *zds;
380:
381: #define conv_digit(c) \
382: (!ISASCII(c) ? -1 : \
383: isdigit(c) ? ((c) - '0') : \
384: islower(c) ? ((c) - 'a' + 10) : \
385: isupper(c) ? ((c) - 'A' + 10) : \
386: -1)
387:
388: if (!str) {
389: if (badcheck) goto bad;
390: return INT2FIX(0);
391: }
392: while (ISSPACE(*str)) str++;
393:
394: if (str[0] == '+') {
395: str++;
396: }
397: else if (str[0] == '-') {
398: str++;
399: sign = 0;
400: }
401: if (str[0] == '+' || str[0] == '-') {
402: if (badcheck) goto bad;
403: return INT2FIX(0);
404: }
405: if (base <= 0) {
406: if (str[0] == '0') {
407: switch (str[1]) {
408: case 'x': case 'X':
409: base = 16;
410: break;
411: case 'b': case 'B':
412: base = 2;
413: break;
414: case 'o': case 'O':
415: base = 8;
416: break;
417: case 'd': case 'D':
418: base = 10;
419: break;
420: default:
421: base = 8;
422: }
423: }
424: else if (base < -1) {
425: base = -base;
426: }
427: else {
428: base = 10;
429: }
430: }
431: switch (base) {
432: case 2:
433: len = 1;
434: if (str[0] == '0' && (str[1] == 'b'||str[1] == 'B')) {
435: str += 2;
436: }
437: break;
438: case 3:
439: len = 2;
440: break;
441: case 8:
442: if (str[0] == '0' && (str[1] == 'o'||str[1] == 'O'||str[1] == '_')) {
443: str += 2;
444: }
445: case 4: case 5: case 6: case 7:
446: len = 3;
447: break;
448: case 10:
449: if (str[0] == '0' && (str[1] == 'd'||str[1] == 'D')) {
450: str += 2;
451: }
452: case 9: case 11: case 12: case 13: case 14: case 15:
453: len = 4;
454: break;
455: case 16:
456: len = 4;
457: if (str[0] == '0' && (str[1] == 'x'||str[1] == 'X')) {
458: str += 2;
459: }
460: break;
461: default:
462: if (base < 2 || 36 < base) {
463: rb_raise(rb_eArgError, "invalid radix %d", base);
464: }
465: if (base <= 32) {
466: len = 5;
467: }
468: else {
469: len = 6;
470: }
471: break;
472: }
473: if (*str == '0') {
474: while (*++str == '0');
475: if (!(c = *str) || ISSPACE(c)) --str;
476: }
477: c = *str;
478: c = conv_digit(c);
479: if (c < 0 || c >= base) {
480: if (badcheck) goto bad;
481: return INT2FIX(0);
482: }
483: len *= strlen(str)*sizeof(char);
484:
485: if (len <= (sizeof(long)*CHAR_BIT)) {
486: unsigned long val = strtoul(str, &end, base);
487:
488: if (str < end && *end == '_') goto bigparse;
489: if (badcheck) {
490: if (end == str) goto bad;
491: while (*end && ISSPACE(*end)) end++;
492: if (*end) goto bad;
493: }
494:
495: if (POSFIXABLE(val)) {
496: if (sign) return LONG2FIX(val);
497: else {
498: long result = -(long)val;
499: return LONG2FIX(result);
500: }
501: }
502: else {
503: VALUE big = rb_uint2big(val);
504: RBIGNUM_SET_SIGN(big, sign);
505: return bignorm(big);
506: }
507: }
508: bigparse:
509: len = (len/BITSPERDIG)+1;
510: if (badcheck && *str == '_') goto bad;
511:
512: z = bignew(len, sign);
513: zds = BDIGITS(z);
514: for (i=len;i--;) zds[i]=0;
515: while ((c = *str++) != 0) {
516: if (c == '_') {
517: if (badcheck) {
518: if (nondigit) goto bad;
519: nondigit = c;
520: }
521: continue;
522: }
523: else if ((c = conv_digit(c)) < 0) {
524: break;
525: }
526: if (c >= base) break;
527: nondigit = 0;
528: i = 0;
529: num = c;
530: for (;;) {
531: while (i<blen) {
532: num += (BDIGIT_DBL)zds[i]*base;
533: zds[i++] = BIGLO(num);
534: num = BIGDN(num);
535: }
536: if (num) {
537: blen++;
538: continue;
539: }
540: break;
541: }
542: }
543: if (badcheck) {
544: str--;
545: if (s+1 < str && str[-1] == '_') goto bad;
546: while (*str && ISSPACE(*str)) str++;
547: if (*str) {
548: bad:
549: rb_invalid_str(s, "Integer");
550: }
551: }
552:
553: return bignorm(z);
554: }
555:
556: VALUE
557: rb_str_to_inum(VALUE str, int base, int badcheck)
558: {
559: char *s;
560: long len;
561:
562: StringValue(str);
563: if (badcheck) {
564: s = StringValueCStr(str);
565: }
566: else {
567: s = RSTRING_PTR(str);
568: }
569: if (s) {
570: len = RSTRING_LEN(str);
571: if (s[len]) {
572: char *p = ALLOCA_N(char, len+1);
573:
574: MEMCPY(p, s, char, len);
575: p[len] = '\0';
576: s = p;
577: }
578: }
579: return rb_cstr_to_inum(s, base, badcheck);
580: }
581:
582: #if HAVE_LONG_LONG
583:
584: static VALUE
585: rb_ull2big(unsigned LONG_LONG n)
586: {
587: BDIGIT_DBL num = n;
588: long i = 0;
589: BDIGIT *digits;
590: VALUE big;
591:
592: big = bignew(DIGSPERLL, 1);
593: digits = BDIGITS(big);
594: while (i < DIGSPERLL) {
595: digits[i++] = BIGLO(num);
596: num = BIGDN(num);
597: }
598:
599: i = DIGSPERLL;
600: while (i-- && !digits[i]) ;
601: RBIGNUM_SET_LEN(big, i+1);
602: return big;
603: }
604:
605: static VALUE
606: rb_ll2big(LONG_LONG n)
607: {
608: 