?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add $(EXEEXT) to executable targets during installation for MinGW
[suif.git] / src / basesuif / useful / inumbers.cc
blob14f6f7c4efe35cac0b1c75f404dfa13a05f9edfd
1 /* file "inumbers.cc" */
2
3 /* Copyright (c) 1995 Stanford University
4
5 All rights reserved.
6
7 This software is provided under the terms described in
8 the "suif_copyright.h" include file. */
9
10 #include <suif_copyright.h>
11
12 /*
13 * This file implements extended-precision integer arithmetic
14 * routines for the i_integer class.
15 */
16
17 #define _MODULE_ "libuseful.a"
18
19 #define RCS_BASE_FILE useful_inumbers_cc
20
21 #include <suif1/misc.h> /* for definitions of boolean and assert() only */
22 #include "inumbers.h"
23 #include <limits.h>
24 #include <string.h>
25 #include <ctype.h>
26
27 RCS_BASE(
28 "$Id: inumbers.cc,v 1.2 1999/08/25 03:29:30 brm Exp $")
29
30
31 /*----------------------------------------------------------------------*
32 Begin Documentation
33 *----------------------------------------------------------------------*
34
35 The i_integer Class
36 -------------------
37
38 The i_integer class is intended to model the mathematic concept of
39 integers, with some simple extensions for dealing with infinite and
40 undetermined quantities.
41
42 The values representable by the i_integer class include all the finite
43 integer numbers (subject to memory limitations of the machine that are
44 system dependent but large), plus four additional distinguishable
45 non-finite elements. There are of course various mathematical
46 concepts of heirarchies of infinite ordinals and cardinals, but those
47 concepts are not useful for the kinds of things we currently plan to
48 use this class for. The kinds of trans-finite concepts we do
49 represent are based on what the system will be used for.
50
51 These four new elements are ``positive infinity'', ``negative
52 infinity'', ``unsigned infinity'' , and ``undetermined''.
53
54 The purpose of ``unsigned infinity'' and ``undetermined'' is to make
55 multiplication and division defined over the whole class: ``unsigned
56 infinity'' essentially represents ``1/0'' and ``undetermined''
57 represents ``0/0''. Neither of these quantities may be compared with
58 ``greater than'' or ``less than'' comparisons with anything, and
59 ``undetermined'' may not be compared for equality with anything
60 either.
61
62 The purpose of ``positive infinity'' and ``negative infinity'' is to
63 have upper and lower bounds to represent unlimited ranges. The
64 distinction between positive and negative must be made for this
65 purpose, but this wouldn't work with ``1/0'' because we want ``-1/0 =
66 1/-0 = 1/0'' by the axioms for ordinary division, so we cannot
67 distinguish sign in the result of dividing by zero. Hence ``unsigned
68 infinity'' is a different concept from either ``positive infinity'' or
69 ``negative infinity''.
70
71 The rules for addition, subtraction, negation, multiplication,
72 reciprication, and division involving these trans-finite elements are
73 defined as follows:
74 (1) Any finite number added to or subtracted from a trans-finite
75 gives the same transfinite.
76 (2) Any finite number minus a transfinite gives the negation of the
77 trans-finite.
78 (3) Negation of ``positive infinity'' gives ``negative infinity''
79 and vice-versa; negation of either of ``unsigned infinity'' or
80 ``undetermined'' gives back the same trans-finite.
81 (4) Multiplication of any trans-finite by a positive finite gives
82 back the same trans-finite; multiplication of any transfinite by
83 a negative finite gives the negation of the trans-finite;
84 multiplication of zero by any trans-finite gives back
85 ``undetermined''.
86 (5) The reciprical of zero is ``unsigned infinity''; the reciprical
87 of ``unsigned infinity'', ``positive infinity'', and ``negative
88 infinity'' are all zero; and the reciprical of ``undetermined''
89 is ``undetermined''.
90 (6) Division is defined as multiplication of the numerator by the
91 reciprical of the denominator.
92 (7) Either of ``positive infinity'' or ``negative infinity'' added
93 to itself is the same trans-finite back; any other case of
94 addition of trans-finites gives ``undetermined''.
95 (8) ``positive infinity'' times itself or ``negative infinity''
96 times itself is ``positive infinity''; ``positive infinity''
97 times ``negative infinity'' is ``negative infinity''; ``unsigned
98 infinity'' times itself is ``unsigned infinity''; any other case
99 of multiplication by two trans-finites gives ``undetermined''.
100
101
102 Implementation
103 --------------
104
105 The implementations of these functions have time complexity O(n) for
106 addition and subtraction, O(n^log_2(3)) for multiplication and base
107 change (including all the bit-wise operations, which are implemented
108 with base change), and O(n^2) for division, where ``n'' is the length
109 of the larger of the string operands (the log of the integer value).
110
111
112 *----------------------------------------------------------------------*
113 End Documentation
114 *----------------------------------------------------------------------*/
115 /*----------------------------------------------------------------------*
116 Begin Macro Definitions
117 *----------------------------------------------------------------------*/
118
119 /* The following is strangely defined because we only use it for
120 * machines on which LONG_MAX + LONG_MIN >= 0 and we want to avoid
121 * compiler warnings about overflow in constant expressions on other
122 * machines. NEG_INT_MIN is similar. */
123
124 #define NEG_LONG_MIN (((long)(LONG_MAX + LONG_MIN >= 0 ? 0 : LONG_MIN)) - \
125 LONG_MIN)
126 #define NEG_INT_MIN (((int)(INT_MAX + INT_MIN >= 0 ? 0 : INT_MIN)) - INT_MIN)
127
128 /*----------------------------------------------------------------------*
129 End Macro Definitions
130 *----------------------------------------------------------------------*/
131 /*----------------------------------------------------------------------*
132 Begin Constant Declarations
133 *----------------------------------------------------------------------*/
134
135 /* CUTOFF must be at least 4 */
136 #define CUTOFF 10
137
138 /*----------------------------------------------------------------------*
139 End Constant Declarations
140 *----------------------------------------------------------------------*/
141 /*----------------------------------------------------------------------*
142 Begin Type Declarations
143 *----------------------------------------------------------------------*/
144
145 class string_integer
146 {
147 public:
148 unsigned long link_count;
149 char *the_digits;
150 boolean is_negative;
151
152 string_integer(unsigned long num_digits)
153 {
154 link_count = 1;
155 the_digits = new char[num_digits + 1];
156 is_negative = FALSE;
157 }
158 ~string_integer()
159 {
160 assert(link_count == 0);
161 delete[] the_digits;
162 }
163 };
164
165 enum binary_bit_ops { BBO_XOR, BBO_AND, BBO_IOR };
166
167 /*----------------------------------------------------------------------*
168 End Type Declarations
169 *----------------------------------------------------------------------*/
170 /*----------------------------------------------------------------------*
171 Begin Private Global Variables
172 *----------------------------------------------------------------------*/
173
174 /*----------------------------------------------------------------------*
175 End Private Global Variables
176 *----------------------------------------------------------------------*/
177 /*----------------------------------------------------------------------*
178 Begin Private Function Declarations
179 *----------------------------------------------------------------------*/
180
181 static void add_link(string_integer *the_si);
182 static void cut_link(string_integer *the_si);
183 static string_integer *add_string_integers(string_integer *op1,
184 string_integer *op2);
185 static string_integer *multiply_string_integers(string_integer *op1,
186 string_integer *op2);
187 static string_integer *div_string_integers(string_integer *op1,
188 string_integer *op2);
189 static string_integer *mod_string_integers(string_integer *op1,
190 string_integer *op2);
191 static string_integer *bitwise_op_string_integers(string_integer *op1,
192 string_integer *op2,
193 binary_bit_ops op);
194 static string_integer *right_shift_string_integers(string_integer *op1,
195 string_integer *op2);
196 static boolean string_integer_fits_long(string_integer *the_si);
197 static long long_from_string_integer(string_integer *the_si);
198 static string_integer *string_integer_from_long(long the_long);
199 static string_integer *string_integer_from_unsigned_long(
200 unsigned long the_ulong);
201 static void string_integer_to_binary(unsigned char **result,
202 unsigned long *result_size,
203 int *carry_bit,
204 string_integer *the_si);
205 static string_integer *binary_to_string_integer(unsigned char *bits,
206 unsigned long bit_size,
207 int carry_bit);
208 static boolean string_magnitude_is_less(char *op1, char *op2,
209 unsigned long op1_len,
210 unsigned long op2_len, int offset);
211 static void add_string_magnitudes(char *result, char *op1, char *op2,
212 unsigned long op1_len,
213 unsigned long op2_len, int base, int offset);
214 static void add_to_string_magnitude(char *result, char *op2,
215 unsigned long result_len,
216 unsigned long op2_len, int base,
217 int offset);
218 static void subtract_string_magnitudes(char *result, char *op1, char *op2,
219 unsigned long op1_len,
220 unsigned long op2_len, int base,
221 int offset);
222 static void multiply_string_magnitudes(char *result, char *scratch, char *op1,
223 char *op2, unsigned long op1_len,
224 unsigned long op2_len, int base,
225 int offset);
226 static void divide_string_magnitudes(char *div_result, char *mod_result,
227 char *op1, char *op2,
228 unsigned long op1_len,
229 unsigned long op2_len, int offset);
230 static void justify_int_string(char *string, unsigned long size, int offset);
231 static void base_convert(char *new_string, char *scratch, char *old_string,
232 unsigned long old_size, int old_base, int new_base,
233 int old_offset, int new_offset);
234 static int blow_up_factor(int old_base, int new_base);
235 static i_rational read_digits_with_decimal_point(const char **location,
236 int base);
237
238 /*----------------------------------------------------------------------*
239 End Private Function Declarations
240 *----------------------------------------------------------------------*/
241 /*----------------------------------------------------------------------*
242 Begin Public Method Implementations
243 *----------------------------------------------------------------------*/
244
245 i_integer::i_integer(const char *initial_string, int base)
246 {
247 the_tag = IIT_UNDETERMINED;
248 read(initial_string, base);
249 }
250
251
252 i_integer::~i_integer()
253 {
254 if (the_tag == IIT_STRING_INT)
255 cut_link(value.si_val);
256 }
257
258
259 boolean i_integer::is_negative(void) const
260 {
261 switch (the_tag)
262 {
263 case IIT_C_INT:
264 return (value.long_val < 0);
265 case IIT_STRING_INT:
266 return (value.si_val->is_negative);
267 case IIT_NEG_INFINITY:
268 return TRUE;
269 default:
270 return FALSE;
271 }
272 }
273
274 boolean i_integer::is_c_char(void) const
275 {
276 return (is_finite() && (*this >= CHAR_MIN) && (*this <= CHAR_MAX));
277 }
278
279 boolean i_integer::is_c_unsigned_char(void) const
280 {
281 return (is_finite() && (*this >= 0) && (*this <= UCHAR_MAX));
282 }
283
284 boolean i_integer::is_c_signed_char(void) const
285 {
286 return (is_finite() && (*this >= SCHAR_MIN) && (*this <= SCHAR_MAX));
287 }
288
289 boolean i_integer::is_c_short(void) const
290 {
291 return (is_finite() && (*this >= SHRT_MIN) && (*this <= SHRT_MAX));
292 }
293
294 boolean i_integer::is_c_unsigned_short(void) const
295 {
296 return (is_finite() && (*this >= 0) && (*this <= USHRT_MAX));
297 }
298
299 boolean i_integer::is_c_int(void) const
300 {
301 return (is_finite() && (*this >= INT_MIN) && (*this <= INT_MAX));
302 }
303
304 boolean i_integer::is_c_unsigned_int(void) const
305 {
306 return (is_finite() && (*this >= 0) && (*this <= UINT_MAX));
307 }
308
309 boolean i_integer::is_c_long(void) const
310 {
311 return (the_tag == IIT_C_INT);
312 }
313
314 boolean i_integer::is_c_unsigned_long(void) const
315 {
316 return (is_finite() && (*this >= 0) && (*this <= ULONG_MAX));
317 }
318
319 char i_integer::c_char(void) const
320 {
321 assert(is_c_char());
322 if (CHAR_MIN == 0)
323 return (char)(c_unsigned_long());
324 else
325 return (char)(c_long());
326 }
327
328 unsigned char i_integer::c_unsigned_char(void) const
329 {
330 assert(is_c_unsigned_char());
331 return (unsigned char)(c_unsigned_long());
332 }
333
334 signed char i_integer::c_signed_char(void) const
335 {
336 assert(is_c_signed_char());
337 return (signed char)(c_long());
338 }
339
340 short i_integer::c_short(void) const
341 {
342 assert(is_c_short());
343 return (short)(c_long());
344 }
345
346 unsigned short i_integer::c_unsigned_short(void) const
347 {
348 assert(is_c_unsigned_short());
349 return (unsigned short)(c_unsigned_long());
350 }
351
352 int i_integer::c_int(void) const
353 {
354 assert(is_c_int());
355 return (int)(c_long());
356 }
357
358 unsigned int i_integer::c_unsigned_int(void) const
359 {
360 assert(is_c_unsigned_int());
361 return (unsigned int)(c_unsigned_long());
362 }
363
364 long i_integer::c_long(void) const
365 {
366 assert(the_tag == IIT_C_INT);
367 return value.long_val;
368 }
369
370 unsigned long i_integer::c_unsigned_long(void) const
371 {
372 assert(is_c_unsigned_long());
373 if (the_tag == IIT_C_INT)
374 return (long)(value.long_val);
375
376 assert(the_tag == IIT_STRING_INT);
377 unsigned long result = 0;
378 char *digit_follow = value.si_val->the_digits;
379 while (*digit_follow != 0)
380 {
381 char this_digit = *digit_follow - '0';
382 assert(result <= ((ULONG_MAX - this_digit) / 10));
383 result *= 10;
384 result += this_digit;
385 ++digit_follow;
386 }
387 return result;
388 }
389
390 void i_integer::set_c_char(char new_value)
391 {
392 set_c_long(new_value);
393 }
394
395 void i_integer::set_c_unsigned_char(unsigned char new_value)
396 {
397 if (new_value > (unsigned long)LONG_MAX)
398 set_c_unsigned_long(new_value);
399 else
400 set_c_long(new_value);
401 }
402
403 void i_integer::set_c_signed_char(signed char new_value)
404 {
405 clear();
406 the_tag = IIT_C_INT;
407 value.long_val = new_value;
408 }
409
410 void i_integer::set_c_short(short new_value)
411 {
412 clear();
413 the_tag = IIT_C_INT;
414 value.long_val = new_value;
415 }
416
417 void i_integer::set_c_unsigned_short(unsigned short new_value)
418 {
419 if (new_value > (unsigned long)LONG_MAX)
420 set_c_unsigned_long(new_value);
421 else
422 set_c_long(new_value);
423 }
424
425 void i_integer::set_c_int(int new_value)
426 {
427 clear();
428 the_tag = IIT_C_INT;
429 value.long_val = new_value;
430 }
431
432 void i_integer::set_c_unsigned_int(unsigned int new_value)
433 {
434 if (new_value > (unsigned long)LONG_MAX)
435 set_c_unsigned_long(new_value);
436 else
437 set_c_long(new_value);
438 }
439
440 void i_integer::set_c_long(long new_value)
441 {
442 clear();
443 the_tag = IIT_C_INT;
444 value.long_val = new_value;
445 }
446
447 void i_integer::set_c_unsigned_long(unsigned long new_value)
448 {
449 clear();
450 if (new_value <= (unsigned long)LONG_MAX)
451 {
452 set_c_long(new_value);
453 return;
454 }
455
456 the_tag = IIT_STRING_INT;
457 value.si_val = string_integer_from_unsigned_long(new_value);
458 }
459
460 void i_integer::set_integer(const i_integer &new_value)
461 {
462 if (&new_value == this) return;
463 clear();
464 the_tag = new_value.the_tag;
465 switch (the_tag)
466 {
467 case IIT_C_INT:
468 value.long_val = new_value.value.long_val;
469 break;
470 case IIT_STRING_INT:
471 value.si_val = new_value.value.si_val;
472 add_link(value.si_val);
473 break;
474 default:
475 break;
476 }
477 }
478
479 void i_integer::clear(void)
480 {
481 if (the_tag == IIT_STRING_INT)
482 cut_link(value.si_val);
483 the_tag = IIT_UNDETERMINED;
484 }
485
486 i_integer i_integer::written_length(int base) const
487 {
488 assert((base > 1) && (base <= 36));
489
490 switch (the_tag)
491 {
492 case IIT_C_INT:
493 {
494 long remaining_value = value.long_val;
495 if (remaining_value == 0)
496 return 1;
497
498 long result;
499 if (remaining_value < 0)
500 {
501 result = 1;
502 while (remaining_value != 0)
503 {
504 long this_digit = remaining_value % base;
505 remaining_value /= base;
506 if (this_digit > 0)
507 ++remaining_value;
508 ++result;
509 }
510 }
511 else
512 {
513 result = 0;
514 while (remaining_value != 0)
515 {
516 remaining_value /= base;
517 ++result;
518 }
519 }
520 return result;
521 }
522 case IIT_STRING_INT:
523 {
524 if (base == 10)
525 {
526 return (strlen(value.si_val->the_digits) +
527 (value.si_val->is_negative ? 1 : 0));
528 }
529
530 static char *scratch_buffer = NULL;
531 static unsigned long scratch_size = 0;
532
533 char *this_digits = value.si_val->the_digits;
534 unsigned long decimal_size = strlen(this_digits);
535
536 unsigned long result_size =
537 blow_up_factor(10, base) * decimal_size;
538
539 if ((scratch_buffer == NULL) || (scratch_size < 10 * result_size))
540 {
541 if (scratch_buffer != NULL)
542 delete[] scratch_buffer;
543 scratch_size = 10 * result_size;
544 scratch_buffer = new char[scratch_size];
545 }
546
547 base_convert(scratch_buffer, &(scratch_buffer[result_size]),
548 this_digits, decimal_size, 10, base, '0', 0);
549
550 char *follow_result = scratch_buffer;
551 char *result_end = &(scratch_buffer[result_size - 1]);
552 while (*follow_result == 0)
553 {
554 assert(follow_result != result_end);
555 ++follow_result;
556 }
557
558 return ((result_end - follow_result) +
559 (value.si_val->is_negative ? 1 : 0));
560 }
561 case IIT_POS_INFINITY:
562 return 4;
563 case IIT_NEG_INFINITY:
564 return 4;
565 case IIT_SIGNLESS_INFINITY:
566 return 3;
567 case IIT_UNDETERMINED:
568 return 2;
569 default:
570 assert(FALSE);
571 return 0;
572 }
573 }
574
575 void i_integer::write(char *location, int base) const
576 {
577 assert((base > 1) && (base <= 36));
578
579 switch (the_tag)
580 {
581 case IIT_C_INT:
582 if (base == 10)
583 {
584 sprintf(location, "%ld", value.long_val);
585 }
586 else
587 {
588 char *follow_location = location;
589 long remaining_value = value.long_val;
590 if (remaining_value == 0)
591 {
592 *follow_location = '0';
593 ++follow_location;
594 }
595 else if (remaining_value < 0)
596 {
597 *follow_location = '-';
598 ++follow_location;
599 while (remaining_value != 0)
600 {
601 long this_digit = remaining_value % base;
602 remaining_value /= base;
603 if (this_digit > 0)
604 {
605 this_digit -= base;
606 ++remaining_value;
607 }
608 this_digit = -this_digit;
609 if (this_digit <= 9)
610 *follow_location = this_digit + '0';
611 else
612 *follow_location = (this_digit - 10) + 'a';
613 ++follow_location;
614 }
615 }
616 else
617 {
618 while (remaining_value != 0)
619 {
620 long this_digit = remaining_value % base;
621 remaining_value /= base;
622 if (this_digit <= 9)
623 *follow_location = this_digit + '0';
624 else
625 *follow_location = (this_digit - 10) + 'a';
626 ++follow_location;
627 }
628 }
629 *follow_location = 0;
630 }
631 break;
632 case IIT_STRING_INT:
633 {
634 char *follow_location = location;
635 if (value.si_val->is_negative)
636 {
637 sprintf(follow_location, "-");
638 ++follow_location;
639 }
640 if (base == 10)
641 {
642 strcpy(follow_location, value.si_val->the_digits);
643 }
644 else
645 {
646 static char *scratch_buffer = NULL;
647 static unsigned long scratch_size = 0;
648
649 char *this_digits = value.si_val->the_digits;
650 unsigned long decimal_size = strlen(this_digits);
651
652 unsigned long result_size =
653 blow_up_factor(10, base) * decimal_size;
654
655 if ((scratch_buffer == NULL) ||
656 (scratch_size < 10 * result_size))
657 {
658 if (scratch_buffer != NULL)
659 delete[] scratch_buffer;
660 scratch_size = 10 * result_size;
661 scratch_buffer = new char[scratch_size];
662 }
663
664 base_convert(scratch_buffer, &(scratch_buffer[result_size]),
665 this_digits, decimal_size, 10, base, '0', 0);
666
667 char *follow_result = scratch_buffer;
668 char *result_end = &(scratch_buffer[result_size - 1]);
669 while (*follow_result == 0)
670 {
671 assert(follow_result != result_end);
672 ++follow_result;
673 }
674
675 while (follow_result != result_end)
676 {
677 int this_digit = *follow_result;
678 if (this_digit <= 9)
679 *follow_location = this_digit + '0';
680 else
681 *follow_location = (this_digit - 10) + 'a';
682 ++follow_location;
683 ++follow_result;
684 }
685
686 *follow_location = 0;
687 }
688 break;
689 }
690 case IIT_POS_INFINITY:
691 strcpy(location, "+Inf");
692 break;
693 case IIT_NEG_INFINITY:
694 strcpy(location, "-Inf");
695 break;
696 case IIT_SIGNLESS_INFINITY:
697 strcpy(location, "Inf");
698 break;
699 case IIT_UNDETERMINED:
700 strcpy(location, "??");
701 break;
702 default:
703 assert(FALSE);
704 }
705 }
706
707 void i_integer::read(const char *location, int base)
708 {
709 assert((base > 1) && (base <= 36));
710
711 static char *scratch_buffer = NULL;
712 static unsigned long scratch_size = 0;
713
714 clear();
715
716 const char *remaining_string = location;
717 boolean is_negative = FALSE;
718
719 while (isspace(*remaining_string))
720 ++remaining_string;
721
722 if (strncmp(remaining_string, "+Inf", 4) == 0)
723 {
724 the_tag = IIT_POS_INFINITY;
725 return;
726 }
727 else if (strncmp(remaining_string, "-Inf", 4) == 0)
728 {
729 the_tag = IIT_NEG_INFINITY;
730 return;
731 }
732 else if (strncmp(remaining_string, "Inf", 3) == 0)
733 {
734 the_tag = IIT_SIGNLESS_INFINITY;
735 return;
736 }
737 else if (strncmp(remaining_string, "??", 4) == 0)
738 {
739 the_tag = IIT_UNDETERMINED;
740 return;
741 }
742
743 if (*remaining_string == '-')
744 {
745 is_negative = TRUE;
746 ++remaining_string;
747 }
748
749 while (isspace(*remaining_string))
750 ++remaining_string;
751
752 const char *follow_string = remaining_string;
753 long this_long = 0;
754 boolean overflow = FALSE;
755 while (*follow_string != 0)
756 {
757 int this_digit = *follow_string;
758 if ((this_digit >= '0') && (this_digit <= '9'))
759 this_digit -= '0';
760 else if ((this_digit >= 'a') && (this_digit <= 'z'))
761 this_digit -= ('a' - 10);
762 else if ((this_digit >= 'A') && (this_digit <= 'Z'))
763 this_digit -= ('A' - 10);
764 else
765 break;
766
767 if (this_digit >= base)
768 break;
769
770 if (is_negative)
771 {
772 if (this_long <
773 (LONG_MIN / base) + (((LONG_MIN % base) < 0) ? 1 : 0))
774 {
775 overflow = TRUE;
776 break;
777 }
778 this_long *= base;
779 if (this_long < LONG_MIN + this_digit)
780 {
781 overflow = TRUE;
782 break;
783 }
784 this_long -= this_digit;
785 }
786 else
787 {
788 if (this_long > LONG_MAX / base)
789 {
790 overflow = TRUE;
791 break;
792 }
793 this_long *= base;
794 if (this_long > LONG_MAX - this_digit)
795 {
796 overflow = TRUE;
797 break;
798 }
799 this_long += this_digit;
800 }
801
802 ++follow_string;
803 }
804
805 if (!overflow)
806 {
807 the_tag = IIT_C_INT;
808 value.long_val = this_long;
809 return;
810 }
811
812 while (*follow_string != 0)
813 {
814 int this_digit = *follow_string;
815 if ((this_digit >= '0') && (this_digit <= '9'))
816 this_digit -= '0';
817 else if ((this_digit >= 'a') && (this_digit <= 'z'))
818 this_digit -= ('a' - 10);
819 else if ((this_digit >= 'A') && (this_digit <= 'Z'))
820 this_digit -= ('A' - 10);
821 else
822 break;
823
824 if (this_digit >= base)
825 break;
826
827 ++follow_string;
828 }
829
830 unsigned long string_size = follow_string - remaining_string;
831 unsigned long new_string_size = string_size;
832 if (base > 10)
833 new_string_size = 2 * string_size;
834
835 if ((base != 10) &&
836 ((scratch_buffer == NULL) || (scratch_size < 10 * new_string_size)))
837 {
838 if (scratch_buffer != NULL)
839 delete[] scratch_buffer;
840 scratch_size = 10 * new_string_size;
841 scratch_buffer = new char[scratch_size];
842 }
843
844 string_integer *new_si = new string_integer(new_string_size);
845 new_si->is_negative = is_negative;
846 if (base == 10)
847 {
848 const char *follow_old = remaining_string;
849 char *follow_new = new_si->the_digits;
850 const char *old_end = &(remaining_string[string_size - 1]);
851 while (TRUE)
852 {
853 assert((*follow_old >= '0') && (*follow_old <= '9'));
854 *follow_new = *follow_old;
855 if (follow_old == old_end)
856 break;
857 ++follow_new;
858 ++follow_old;
859 }
860 assert(follow_new == &(new_si->the_digits[new_string_size - 1]));
861 }
862 else
863 {
864 const char *follow_old = remaining_string;
865 char *follow_new = scratch_buffer;
866 const char *old_end = &(remaining_string[string_size - 1]);
867 while (TRUE)
868 {
869 int this_digit = *follow_old;
870 if ((this_digit >= '0') && (this_digit <= '9'))
871 this_digit -= '0';
872 else if ((this_digit >= 'a') && (this_digit <= 'z'))
873 this_digit -= ('a' - 10);
874 else if ((this_digit >= 'A') && (this_digit <= 'Z'))
875 this_digit -= ('A' - 10);
876 else
877 assert(FALSE);
878
879 *follow_new = this_digit;
880 if (follow_old == old_end)
881 break;
882 ++follow_new;
883 ++follow_old;
884 }
885 assert(follow_new == &(scratch_buffer[string_size - 1]));
886
887 base_convert(new_si->the_digits, &(scratch_buffer[string_size]),
888 scratch_buffer, string_size, base, 10, 0, '0');
889 }
890 justify_int_string(new_si->the_digits, new_string_size, '0');
891
892 the_tag = IIT_STRING_INT;
893 value.si_val = new_si;
894 }
895
896 void i_integer::print(FILE *fp, int base) const
897 {
898 assert((base > 1) && (base <= 36));
899
900 switch (the_tag)
901 {
902 case IIT_C_INT:
903 if (base == 10)
904 {
905 fprintf(fp, "%ld", value.long_val);
906 }
907 else
908 {
909 long remaining_value = value.long_val;
910 if (remaining_value == 0)
911 {
912 fputc('0', fp);
913 }
914 else if (remaining_value < 0)
915 {
916 fputc('-', fp);
917 while (remaining_value != 0)
918 {
919 long this_digit = remaining_value % base;
920 remaining_value /= base;
921 if (this_digit > 0)
922 {
923 this_digit -= base;
924 ++remaining_value;
925 }
926 this_digit = -this_digit;
927 if (this_digit <= 9)
928 fputc(this_digit + '0', fp);
929 else
930 fputc((this_digit - 10) + 'a', fp);
931 }
932 }
933 else
934 {
935 while (remaining_value != 0)
936 {
937 long this_digit = remaining_value % base;
938 remaining_value /= base;
939 if (this_digit <= 9)
940 fputc(this_digit + '0', fp);
941 else
942 fputc((this_digit - 10) + 'a', fp);
943 }
944 }
945 }
946 break;
947 case IIT_STRING_INT:
948 if (value.si_val->is_negative)
949 fputc('-', fp);
950 if (base == 10)
951 {
952 fputs(value.si_val->the_digits, fp);
953 }
954 else
955 {
956 static char *scratch_buffer = NULL;
957 static unsigned long scratch_size = 0;
958
959 char *this_digits = value.si_val->the_digits;
960 unsigned long decimal_size = strlen(this_digits);
961
962 unsigned long result_size =
963 blow_up_factor(10, base) * decimal_size;
964
965 if ((scratch_buffer == NULL) ||
966 (scratch_size < 10 * result_size))
967 {
968 if (scratch_buffer != NULL)
969 delete[] scratch_buffer;
970 scratch_size = 10 * result_size;
971 scratch_buffer = new char[scratch_size];
972 }
973
974 base_convert(scratch_buffer, &(scratch_buffer[result_size]),
975 this_digits, decimal_size, 10, base, '0', 0);
976
977 char *follow_result = scratch_buffer;
978 char *result_end = &(scratch_buffer[result_size - 1]);
979 while (*follow_result == 0)
980 {
981 assert(follow_result != result_end);
982 ++follow_result;
983 }
984
985 while (follow_result != result_end)
986 {
987 int this_digit = *follow_result;
988 if (this_digit <= 9)
989 fputc(this_digit + '0', fp);
990 else
991 fputc((this_digit - 10) + 'a', fp);
992 ++follow_result;
993 }
994 }
995 break;
996 case IIT_POS_INFINITY:
997 fputs("+Inf", fp);
998 break;
999 case IIT_NEG_INFINITY:
1000 fputs("-Inf", fp);
1001 break;
1002 case IIT_SIGNLESS_INFINITY:
1003 fputs("Inf", fp);
1004 break;
1005 case IIT_UNDETERMINED:
1006 fputs("??", fp);
1007 break;
1008 default:
1009 assert(FALSE);
1010 }
1011 }
1012
1013 boolean i_integer::is_equal_to(const i_integer &other) const
1014 {
1015 switch (the_tag)
1016 {
1017 case IIT_C_INT:
1018 return ((other.the_tag == IIT_C_INT) &&
1019 (value.long_val == other.value.long_val));
1020 case IIT_STRING_INT:
1021 return ((other.the_tag == IIT_STRING_INT) &&
1022 (value.si_val->is_negative ==
1023 other.value.si_val->is_negative) &&
1024 (strcmp(value.si_val->the_digits,
1025 other.value.si_val->the_digits) == 0));
1026 case IIT_POS_INFINITY:
1027 return (other.the_tag == IIT_POS_INFINITY);
1028 case IIT_NEG_INFINITY:
1029 return (other.the_tag == IIT_NEG_INFINITY);
1030 case IIT_SIGNLESS_INFINITY:
1031 return (other.the_tag == IIT_SIGNLESS_INFINITY);
1032 case IIT_UNDETERMINED:
1033 return FALSE;
1034 default:
1035 assert(FALSE);
1036 return FALSE;
1037 }
1038 }
1039
1040 boolean i_integer::is_less_than(const i_integer &other) const
1041 {
1042 switch (the_tag)
1043 {
1044 case IIT_C_INT:
1045 switch (other.the_tag)
1046 {
1047 case IIT_C_INT:
1048 return (value.long_val < other.value.long_val);
1049 case IIT_STRING_INT:
1050 return !(other.value.si_val->is_negative);
1051 case IIT_POS_INFINITY:
1052 return TRUE;
1053 case IIT_NEG_INFINITY:
1054 return FALSE;
1055 case IIT_SIGNLESS_INFINITY:
1056 return FALSE;
1057 case IIT_UNDETERMINED:
1058 return FALSE;
1059 default:
1060 assert(FALSE);
1061 return FALSE;
1062 }
1063 case IIT_STRING_INT:
1064 switch (other.the_tag)
1065 {
1066 case IIT_C_INT:
1067 return value.si_val->is_negative;
1068 case IIT_STRING_INT:
1069 {
1070 if (value.si_val->is_negative &&
1071 !other.value.si_val->is_negative)
1072 {
1073 return TRUE;
1074 }
1075 else if ((!value.si_val->is_negative) &&
1076 other.value.si_val->is_negative)
1077 {
1078 return FALSE;
1079 }
1080
1081 char *this_digits = value.si_val->the_digits;
1082 char *other_digits = other.value.si_val->the_digits;
1083 unsigned long this_count = strlen(this_digits);
1084 unsigned long other_count = strlen(other_digits);
1085 return string_magnitude_is_less(this_digits, other_digits,
1086 this_count, other_count,
1087 '0');
1088 }
1089 case IIT_POS_INFINITY:
1090 return TRUE;
1091 case IIT_NEG_INFINITY:
1092 return FALSE;
1093 case IIT_SIGNLESS_INFINITY:
1094 return FALSE;
1095 case IIT_UNDETERMINED:
1096 return FALSE;
1097 default:
1098 assert(FALSE);
1099 return FALSE;
1100 }
1101 case IIT_POS_INFINITY:
1102 return FALSE;
1103 case IIT_NEG_INFINITY:
1104 switch (other.the_tag)
1105 {
1106 case IIT_C_INT:
1107 return TRUE;
1108 case IIT_STRING_INT:
1109 return TRUE;
1110 case IIT_POS_INFINITY:
1111 return TRUE;
1112 case IIT_NEG_INFINITY:
1113 return FALSE;
1114 case IIT_SIGNLESS_INFINITY:
1115 return FALSE;
1116 case IIT_UNDETERMINED:
1117 return FALSE;
1118 default:
1119 assert(FALSE);
1120 return FALSE;
1121 }
1122 case IIT_SIGNLESS_INFINITY:
1123 return FALSE;
1124 case IIT_UNDETERMINED:
1125 return FALSE;
1126 default:
1127 assert(FALSE);
1128 return FALSE;
1129 }
1130 }
1131
1132 boolean i_integer::is_divisible_by(const i_integer &other) const
1133 {
1134 return (div(other) == 0);
1135 }
1136
1137 i_integer i_integer::add(const i_integer &other) const
1138 {
1139 switch (the_tag)
1140 {
1141 case IIT_C_INT:
1142 switch (other.the_tag)
1143 {
1144 case IIT_C_INT:
1145 {
1146 long this_long = value.long_val;
1147 long other_long = other.value.long_val;
1148 if (this_long < 0)
1149 {
1150 if (other_long < 0)
1151 {
1152 if (this_long >= LONG_MIN - other_long)
1153 return i_integer(this_long + other_long);
1154 }
1155 else
1156 {
1157 return i_integer(this_long + other_long);
1158 }
1159 }
1160 else
1161 {
1162 if (other_long < 0)
1163 {
1164 return i_integer(this_long + other_long);
1165 }
1166 else
1167 {
1168 if (this_long <= LONG_MAX - other_long)
1169 return i_integer(this_long + other_long);
1170 }
1171 }
1172
1173 string_integer *si1 = string_integer_from_long(this_long);
1174 string_integer *si2 = string_integer_from_long(other_long);
1175 string_integer *new_si = add_string_integers(si1, si2);
1176 cut_link(si1);
1177 cut_link(si2);
1178 return i_integer(new_si);
1179 }
1180 case IIT_STRING_INT:
1181 {
1182 string_integer *this_si =
1183 string_integer_from_long(value.long_val);
1184 string_integer *other_si = other.value.si_val;
1185 string_integer *new_si =
1186 add_string_integers(this_si, other_si);
1187 cut_link(this_si);
1188 if (string_integer_fits_long(new_si))
1189 {
1190 long new_long = long_from_string_integer(new_si);
1191 cut_link(new_si);
1192 return i_integer(new_long);
1193 }
1194 return i_integer(new_si);
1195 }
1196 case IIT_POS_INFINITY:
1197 case IIT_NEG_INFINITY:
1198 case IIT_SIGNLESS_INFINITY:
1199 return other;
1200 case IIT_UNDETERMINED:
1201 return i_integer();
1202 default:
1203 assert(FALSE);
1204 return i_integer();
1205 }
1206 case IIT_STRING_INT:
1207 switch (other.the_tag)
1208 {
1209 case IIT_C_INT:
1210 {
1211 string_integer *this_si = value.si_val;
1212 string_integer *other_si =
1213 string_integer_from_long(other.value.long_val);
1214 string_integer *new_si =
1215 add_string_integers(this_si, other_si);
1216 cut_link(other_si);
1217 if (string_integer_fits_long(new_si))
1218 {
1219 long new_long = long_from_string_integer(new_si);
1220 cut_link(new_si);
1221 return i_integer(new_long);
1222 }
1223 return i_integer(new_si);
1224 }
1225 case IIT_STRING_INT:
1226 {
1227 string_integer *this_si = value.si_val;
1228 string_integer *other_si = other.value.si_val;
1229 string_integer *new_si =
1230 add_string_integers(this_si, other_si);
1231 if (this_si->is_negative != other_si->is_negative)
1232 {
1233 if (string_integer_fits_long(new_si))
1234 {
1235 long new_long = long_from_string_integer(new_si);
1236 cut_link(new_si);
1237 return i_integer(new_long);
1238 }
1239 }
1240 return i_integer(new_si);
1241 }
1242 case IIT_POS_INFINITY:
1243 case IIT_NEG_INFINITY:
1244 case IIT_SIGNLESS_INFINITY:
1245 return other;
1246 case IIT_UNDETERMINED:
1247 return i_integer();
1248 default:
1249 assert(FALSE);
1250 return i_integer();
1251 }
1252 case IIT_POS_INFINITY:
1253 switch (other.the_tag)
1254 {
1255 case IIT_C_INT:
1256 case IIT_STRING_INT:
1257 case IIT_POS_INFINITY:
1258 return *this;
1259 case IIT_NEG_INFINITY:
1260 case IIT_SIGNLESS_INFINITY:
1261 case IIT_UNDETERMINED:
1262 return i_integer();
1263 default:
1264 assert(FALSE);
1265 return i_integer();
1266 }
1267 case IIT_NEG_INFINITY:
1268 switch (other.the_tag)
1269 {
1270 case IIT_C_INT:
1271 case IIT_STRING_INT:
1272 case IIT_NEG_INFINITY:
1273 return *this;
1274 case IIT_POS_INFINITY:
1275 case IIT_SIGNLESS_INFINITY:
1276 case IIT_UNDETERMINED:
1277 return i_integer();
1278 default:
1279 assert(FALSE);
1280 return i_integer();
1281 }
1282 case IIT_SIGNLESS_INFINITY:
1283 switch (other.the_tag)
1284 {
1285 case IIT_C_INT:
1286 case IIT_STRING_INT:
1287 return *this;
1288 case IIT_POS_INFINITY:
1289 case IIT_NEG_INFINITY:
1290 case IIT_SIGNLESS_INFINITY:
1291 case IIT_UNDETERMINED:
1292 return i_integer();
1293 default:
1294 assert(FALSE);
1295 return i_integer();
1296 }
1297 case IIT_UNDETERMINED:
1298 return i_integer();
1299 default:
1300 assert(FALSE);
1301 return i_integer();
1302 }
1303 }
1304
1305 i_integer i_integer::subtract(const i_integer &other) const
1306 {
1307 i_integer other_negation = other.negate();
1308 return add(other_negation);
1309 }
1310
1311 i_integer i_integer::multiply(const i_integer &other) const
1312 {
1313 switch (the_tag)
1314 {
1315 case IIT_C_INT:
1316 switch (other.the_tag)
1317 {
1318 case IIT_C_INT:
1319 {
1320 long this_long = value.long_val;
1321 long other_long = other.value.long_val;
1322 if ((this_long == 0) || (other_long == 0))
1323 return i_integer(0);
1324 if (this_long < 0)
1325 {
1326 if (other_long < 0)
1327 {
1328 if ((LONG_MAX + LONG_MIN) >= 0)
1329 {
1330 if (-this_long <= LONG_MAX / -other_long)
1331 return i_integer(this_long * other_long);
1332 }
1333 else
1334 {
1335 if (this_long > LONG_MAX / other_long)
1336 return i_integer(this_long * other_long);
1337 }
1338 }
1339 else
1340 {
1341 if ((LONG_MAX + LONG_MIN) >= 0)
1342 {
1343 if (-this_long <= NEG_LONG_MIN / other_long)
1344 return i_integer(this_long * other_long);
1345 }
1346 else
1347 {
1348 if (this_long > LONG_MIN / other_long)
1349 return i_integer(this_long * other_long);
1350 }
1351 }
1352 }
1353 else
1354 {
1355 if (other_long < 0)
1356 {
1357 if ((LONG_MAX + LONG_MIN) >= 0)
1358 {
1359 if (this_long <= NEG_LONG_MIN / -other_long)
1360 return i_integer(this_long * other_long);
1361 }
1362 else
1363 {
1364 if (other_long > LONG_MIN / this_long)
1365 return i_integer(this_long * other_long);
1366 }
1367 }
1368 else
1369 {
1370 if (this_long <= LONG_MAX / other_long)
1371 return i_integer(this_long * other_long);
1372 }
1373 }
1374
1375 string_integer *si1 = string_integer_from_long(this_long);
1376 string_integer *si2 = string_integer_from_long(other_long);
1377 string_integer *new_si =
1378 multiply_string_integers(si1, si2);
1379 cut_link(si1);
1380 cut_link(si2);
1381 return i_integer(new_si);
1382 }
1383 case IIT_STRING_INT:
1384 {
1385 string_integer *this_si =
1386 string_integer_from_long(value.long_val);
1387 string_integer *other_si = other.value.si_val;
1388 string_integer *new_si =
1389 multiply_string_integers(this_si, other_si);
1390 cut_link(this_si);
1391 if (string_integer_fits_long(new_si))
1392 {
1393 long new_long = long_from_string_integer(new_si);
1394 cut_link(new_si);
1395 return i_integer(new_long);
1396 }
1397 return i_integer(new_si);
1398 }
1399 case IIT_POS_INFINITY:
1400 case IIT_NEG_INFINITY:
1401 if (value.long_val == 0)
1402 return i_integer();
1403 else if (value.long_val < 0)
1404 return other.negate();
1405 else
1406 return other;
1407 case IIT_SIGNLESS_INFINITY:
1408 return other;
1409 case IIT_UNDETERMINED:
1410 return i_integer();
1411 default:
1412 assert(FALSE);
1413 return i_integer();
1414 }
1415 case IIT_STRING_INT:
1416 switch (other.the_tag)
1417 {
1418 case IIT_C_INT:
1419 {
1420 string_integer *this_si = value.si_val;
1421 string_integer *other_si =
1422 string_integer_from_long(other.value.long_val);
1423 string_integer *new_si =
1424 multiply_string_integers(this_si, other_si);
1425 cut_link(other_si);
1426 if (string_integer_fits_long(new_si))
1427 {
1428 long new_long = long_from_string_integer(new_si);
1429 cut_link(new_si);
1430 return i_integer(new_long);
1431 }
1432 return i_integer(new_si);
1433 }
1434 case IIT_STRING_INT:
1435 {
1436 string_integer *this_si = value.si_val;
1437 string_integer *other_si = other.value.si_val;
1438 string_integer *new_si =
1439 multiply_string_integers(this_si, other_si);
1440 if (string_integer_fits_long(new_si))
1441 {
1442 long new_long = long_from_string_integer(new_si);
1443 cut_link(new_si);
1444 return i_integer(new_long);
1445 }
1446 return i_integer(new_si);
1447 }
1448 case IIT_POS_INFINITY:
1449 case IIT_NEG_INFINITY:
1450 if (is_negative())
1451 return other.negate();
1452 else
1453 return other;
1454 case IIT_SIGNLESS_INFINITY:
1455 return other;
1456 case IIT_UNDETERMINED:
1457 return i_integer();
1458 default:
1459 assert(FALSE);
1460 return i_integer();
1461 }
1462 case IIT_POS_INFINITY:
1463 case IIT_NEG_INFINITY:
1464 switch (other.the_tag)
1465 {
1466 case IIT_C_INT:
1467 if (other.value.long_val == 0)
1468 return i_integer();
1469 /* fall through */
1470 case IIT_STRING_INT:
1471 if (other.is_negative())
1472 return negate();
1473 else
1474 return *this;
1475 case IIT_POS_INFINITY:
1476 return *this;
1477 case IIT_NEG_INFINITY:
1478 return negate();
1479 case IIT_SIGNLESS_INFINITY:
1480 return other;
1481 case IIT_UNDETERMINED:
1482 return i_integer();
1483 default:
1484 assert(FALSE);
1485 return i_integer();
1486 }
1487 case IIT_SIGNLESS_INFINITY:
1488 switch (other.the_tag)
1489 {
1490 case IIT_C_INT:
1491 if (other.value.long_val == 0)
1492 return i_integer();
1493 /* fall through */
1494 case IIT_STRING_INT:
1495 case IIT_POS_INFINITY:
1496 case IIT_NEG_INFINITY:
1497 case IIT_SIGNLESS_INFINITY:
1498 return *this;
1499 case IIT_UNDETERMINED:
1500 return i_integer();
1501 default:
1502 assert(FALSE);
1503 return i_integer();
1504 }
1505 case IIT_UNDETERMINED:
1506 return i_integer();
1507 default:
1508 assert(FALSE);
1509 return i_integer();
1510 }
1511 }
1512
1513 i_integer i_integer::div(const i_integer &other) const
1514 {
1515 switch (the_tag)
1516 {
1517 case IIT_C_INT:
1518 switch (other.the_tag)
1519 {
1520 case IIT_C_INT:
1521 {
1522 long this_long = value.long_val;
1523 long other_long = other.value.long_val;
1524 if (other_long == 0)
1525 {
1526 if (this_long == 0)
1527 {
1528 return i_integer();
1529 }
1530 else
1531 {
1532 i_integer result;
1533 result.the_tag = IIT_SIGNLESS_INFINITY;
1534 return result;
1535 }
1536 }
1537
1538 if (this_long == 0)
1539 return i_integer(0);
1540 if (other_long == 1)
1541 return i_integer(this_long);
1542
1543 if (this_long < 0)
1544 {
1545 if (other_long < 0)
1546 {
1547 if ((LONG_MAX + LONG_MIN) >= 0)
1548 {
1549 return i_integer((-this_long) / (-other_long));
1550 }
1551 else
1552 {
1553 if ((this_long >= -LONG_MAX) &&
1554 (other_long >= -LONG_MAX))
1555 {
1556 return i_integer((-this_long) /
1557 (-other_long));
1558 }
1559 }
1560 }
1561 else
1562 {
1563 if ((LONG_MAX + LONG_MIN) == 0)
1564 {
1565 return i_integer(-((-this_long) / other_long));
1566 }
1567 else if ((LONG_MAX + LONG_MIN) > 0)
1568 {
1569 if ((-this_long) / other_long <= NEG_LONG_MIN)
1570 {
1571 return i_integer(-((-this_long) /
1572 other_long));
1573 }
1574 }
1575 else
1576 {
1577 if (this_long >= -LONG_MAX)
1578 {
1579 return i_integer(-((-this_long) /
1580 other_long));
1581 }
1582 }
1583 }
1584 }
1585 else
1586 {
1587 if (other_long < 0)
1588 {
1589 if ((LONG_MAX + LONG_MIN) == 0)
1590 {
1591 return i_integer(-(this_long / (-other_long)));
1592 }
1593 else if ((LONG_MAX + LONG_MIN) > 0)
1594 {
1595 if (this_long / (-other_long) <= NEG_LONG_MIN)
1596 {
1597 return i_integer(-(this_long /
1598 (-other_long)));
1599 }
1600 }
1601 else
1602 {
1603 if (other_long >= -LONG_MAX)
1604 {
1605 return i_integer(-(this_long /
1606 (-other_long)));
1607 }
1608 }
1609 }
1610 else
1611 {
1612 return i_integer(this_long / other_long);
1613 }
1614 }
1615
1616 string_integer *si1 = string_integer_from_long(this_long);
1617 string_integer *si2 = string_integer_from_long(other_long);
1618 string_integer *new_si = div_string_integers(si1, si2);
1619 cut_link(si1);
1620 cut_link(si2);
1621 if (string_integer_fits_long(new_si))
1622 {
1623 long new_long = long_from_string_integer(new_si);
1624 cut_link(new_si);
1625 return i_integer(new_long);
1626 }
1627 return i_integer(new_si);
1628 }
1629 case IIT_STRING_INT:
1630 {
1631 string_integer *this_si =
1632 string_integer_from_long(value.long_val);
1633 string_integer *other_si = other.value.si_val;
1634 string_integer *new_si =
1635 div_string_integers(this_si, other_si);
1636 cut_link(this_si);
1637 if (string_integer_fits_long(new_si))
1638 {
1639 long new_long = long_from_string_integer(new_si);
1640 cut_link(new_si);
1641 return i_integer(new_long);
1642 }
1643 return i_integer(new_si);
1644 }
1645 case IIT_POS_INFINITY:
1646 case IIT_NEG_INFINITY:
1647 case IIT_SIGNLESS_INFINITY:
1648 return i_integer(0);
1649 case IIT_UNDETERMINED:
1650 return i_integer();
1651 default:
1652 assert(FALSE);
1653 return i_integer();
1654 }
1655 case IIT_STRING_INT:
1656 switch (other.the_tag)
1657 {
1658 case IIT_C_INT:
1659 {
1660 if (other.value.long_val == 0)
1661 {
1662 i_integer result;
1663 result.the_tag = IIT_SIGNLESS_INFINITY;
1664 return result;
1665 }
1666 string_integer *this_si = value.si_val;
1667 string_integer *other_si =
1668 string_integer_from_long(other.value.long_val);
1669 string_integer *new_si =
1670 div_string_integers(this_si, other_si);
1671 cut_link(other_si);
1672 if (string_integer_fits_long(new_si))
1673 {
1674 long new_long = long_from_string_integer(new_si);
1675 cut_link(new_si);
1676 return i_integer(new_long);
1677 }
1678 return i_integer(new_si);
1679 }
1680 case IIT_STRING_INT:
1681 {
1682 string_integer *this_si = value.si_val;
1683 string_integer *other_si = other.value.si_val;
1684 string_integer *new_si =
1685 div_string_integers(this_si, other_si);
1686 if (string_integer_fits_long(new_si))
1687 {
1688 long new_long = long_from_string_integer(new_si);
1689 cut_link(new_si);
1690 return i_integer(new_long);
1691 }
1692 return i_integer(new_si);
1693 }
1694 case IIT_POS_INFINITY:
1695 case IIT_NEG_INFINITY:
1696 case IIT_SIGNLESS_INFINITY:
1697 return i_integer(0);
1698 case IIT_UNDETERMINED:
1699 return i_integer();
1700 default:
1701 assert(FALSE);
1702 return i_integer();
1703 }
1704 case IIT_POS_INFINITY:
1705 case IIT_NEG_INFINITY:
1706 switch (other.the_tag)
1707 {
1708 case IIT_C_INT:
1709 if (other.value.long_val == 0)
1710 return i_integer();
1711 /* fall through */
1712 case IIT_STRING_INT:
1713 if (other.is_negative())
1714 return negate();
1715 else
1716 return *this;
1717 case IIT_POS_INFINITY:
1718 case IIT_NEG_INFINITY:
1719 case IIT_SIGNLESS_INFINITY:
1720 case IIT_UNDETERMINED:
1721 return i_integer();
1722 default:
1723 assert(FALSE);
1724 return i_integer();
1725 }
1726 case IIT_SIGNLESS_INFINITY:
1727 switch (other.the_tag)
1728 {
1729 case IIT_C_INT:
1730 if (other.value.long_val == 0)
1731 return i_integer();
1732 /* fall through */
1733 case IIT_STRING_INT:
1734 return *this;
1735 case IIT_POS_INFINITY:
1736 case IIT_NEG_INFINITY:
1737 case IIT_SIGNLESS_INFINITY:
1738 case IIT_UNDETERMINED:
1739 return i_integer();
1740 default:
1741 assert(FALSE);
1742 return i_integer();
1743 }
1744 case IIT_UNDETERMINED:
1745 return i_integer();
1746 default:
1747 assert(FALSE);
1748 return i_integer();
1749 }
1750 }
1751
1752 i_integer i_integer::mod(const i_integer &other) const
1753 {
1754 switch (the_tag)
1755 {
1756 case IIT_C_INT:
1757 switch (other.the_tag)
1758 {
1759 case IIT_C_INT:
1760 {
1761 long this_long = value.long_val;
1762 long other_long = other.value.long_val;
1763 if (other_long == 0)
1764 return i_integer();
1765
1766 if (this_long == 0)
1767 return i_integer(0);
1768 if (other_long == 1)
1769 return i_integer(0);
1770
1771 if (this_long < 0)
1772 {
1773 if (other_long < 0)
1774 {
1775 if ((LONG_MAX + LONG_MIN) >= 0)
1776 {
1777 return i_integer(-((-this_long) %
1778 (-other_long)));
1779 }
1780 else
1781 {
1782 if ((this_long >= -LONG_MAX) &&
1783 (other_long >= -LONG_MAX))
1784 {
1785 return i_integer(-((-this_long) %
1786 (-other_long)));
1787 }
1788 }
1789 }
1790 else
1791 {
1792 if ((LONG_MAX + LONG_MIN) >= 0)
1793 {
1794 return i_integer(-((-this_long) % other_long));
1795 }
1796 else
1797 {
1798 if (this_long >= -LONG_MAX)
1799 {
1800 return i_integer(-((-this_long) %
1801 other_long));
1802 }
1803 }
1804 }
1805 }
1806 else
1807 {
1808 if (other_long < 0)
1809 {
1810 if ((LONG_MAX + LONG_MIN) >= 0)
1811 {
1812 return i_integer(this_long % (-other_long));
1813 }
1814 else
1815 {
1816 if (other_long >= -LONG_MAX)
1817 {
1818 return i_integer(this_long %
1819 (-other_long));
1820 }
1821 }
1822 }
1823 else
1824 {
1825 return i_integer(this_long % other_long);
1826 }
1827 }
1828
1829 string_integer *si1 = string_integer_from_long(this_long);
1830 string_integer *si2 = string_integer_from_long(other_long);
1831 string_integer *new_si = mod_string_integers(si1, si2);
1832 cut_link(si1);
1833 cut_link(si2);
1834 if (string_integer_fits_long(new_si))
1835 {
1836 long new_long = long_from_string_integer(new_si);
1837 cut_link(new_si);
1838 return i_integer(new_long);
1839 }
1840 return i_integer(new_si);
1841 }
1842 case IIT_STRING_INT:
1843 {
1844 string_integer *this_si =
1845 string_integer_from_long(value.long_val);
1846 string_integer *other_si = other.value.si_val;
1847 string_integer *new_si =
1848 mod_string_integers(this_si, other_si);
1849 cut_link(this_si);
1850 if (string_integer_fits_long(new_si))
1851 {
1852 long new_long = long_from_string_integer(new_si);
1853 cut_link(new_si);
1854 return i_integer(new_long);
1855 }
1856 return i_integer(new_si);
1857 }
1858 case IIT_POS_INFINITY:
1859 case IIT_NEG_INFINITY:
1860 case IIT_SIGNLESS_INFINITY:
1861 return *this;
1862 case IIT_UNDETERMINED:
1863 return i_integer();
1864 default:
1865 assert(FALSE);
1866 return i_integer();
1867 }
1868 case IIT_STRING_INT:
1869 switch (other.the_tag)
1870 {
1871 case IIT_C_INT:
1872 {
1873 if (other.value.long_val == 0)
1874 return i_integer();
1875 string_integer *this_si = value.si_val;
1876 string_integer *other_si =
1877 string_integer_from_long(other.value.long_val);
1878 string_integer *new_si =
1879 mod_string_integers(this_si, other_si);
1880 cut_link(other_si);
1881 if (string_integer_fits_long(new_si))
1882 {
1883 long new_long = long_from_string_integer(new_si);
1884 cut_link(new_si);
1885 return i_integer(new_long);
1886 }
1887 return i_integer(new_si);
1888 }
1889 case IIT_STRING_INT:
1890 {
1891 string_integer *this_si = value.si_val;
1892 string_integer *other_si = other.value.si_val;
1893 string_integer *new_si =
1894 mod_string_integers(this_si, other_si);
1895 if (string_integer_fits_long(new_si))
1896 {
1897 long new_long = long_from_string_integer(new_si);
1898 cut_link(new_si);
1899 return i_integer(new_long);
1900 }
1901 return i_integer(new_si);
1902 }
1903 case IIT_POS_INFINITY:
1904 case IIT_NEG_INFINITY:
1905 case IIT_SIGNLESS_INFINITY:
1906 return *this;
1907 case IIT_UNDETERMINED:
1908 return i_integer();
1909 default:
1910 assert(FALSE);
1911 return i_integer();
1912 }
1913 case IIT_POS_INFINITY:
1914 case IIT_NEG_INFINITY:
1915 case IIT_SIGNLESS_INFINITY:
1916 case IIT_UNDETERMINED:
1917 return i_integer();
1918 default:
1919 assert(FALSE);
1920 return i_integer();
1921 }
1922 }
1923
1924 i_integer i_integer::negate(void) const
1925 {
1926 switch (the_tag)
1927 {
1928 case IIT_C_INT:
1929 if ((LONG_MAX + LONG_MIN) == 0)
1930 {
1931 return i_integer(-(value.long_val));
1932 }
1933 else if ((LONG_MAX + LONG_MIN) > 0)
1934 {
1935 long this_long = value.long_val;
1936 if ((this_long < 0) || (this_long + LONG_MIN <= 0))
1937 return i_integer(-this_long);
1938 string_integer *new_si = string_integer_from_long(this_long);
1939 new_si->is_negative = TRUE;
1940 return i_integer(new_si);
1941 }
1942 else
1943 {
1944 long this_long = value.long_val;
1945 if ((this_long > 0) || (this_long + LONG_MAX >= 0))
1946 return i_integer(-this_long);
1947 string_integer *new_si = string_integer_from_long(this_long);
1948 new_si->is_negative = FALSE;
1949 return i_integer(new_si);
1950 }
1951 case IIT_STRING_INT:
1952 {
1953 char *old_digits = value.si_val->the_digits;
1954 string_integer *new_si = new string_integer(strlen(old_digits));
1955 strcpy(new_si->the_digits, old_digits);
1956 new_si->is_negative = !(value.si_val->is_negative);
1957 if (string_integer_fits_long(new_si))
1958 {
1959 long new_long = long_from_string_integer(new_si);
1960 cut_link(new_si);
1961 return i_integer(new_long);
1962 }
1963 return i_integer(new_si);
1964 }
1965 case IIT_POS_INFINITY:
1966 {
1967 i_integer result;
1968 result.the_tag = IIT_NEG_INFINITY;
1969 return result;
1970 }
1971 case IIT_NEG_INFINITY:
1972 {
1973 i_integer result;
1974 result.the_tag = IIT_POS_INFINITY;
1975 return result;
1976 }
1977 case IIT_SIGNLESS_INFINITY:
1978 case IIT_UNDETERMINED:
1979 return *this;
1980 default:
1981 assert(FALSE);
1982 return i_integer();
1983 }
1984 }
1985
1986 i_integer i_integer::operator^(const i_integer &other) const
1987 {
1988 switch (the_tag)
1989 {
1990 case IIT_C_INT:
1991 switch (other.the_tag)
1992 {
1993 case IIT_C_INT:
1994 {
1995 long this_long = value.long_val;
1996 long other_long = other.value.long_val;
1997
1998 if ((this_long >= 0) && (other_long >= 0))
1999 {
2000 return i_integer(((unsigned long)this_long) ^
2001 ((unsigned long)other_long));
2002 }
2003
2004 string_integer *si1 = string_integer_from_long(this_long);
2005 string_integer *si2 = string_integer_from_long(other_long);
2006 string_integer *new_si =
2007 bitwise_op_string_integers(si1, si2, BBO_XOR);
2008 cut_link(si1);
2009 cut_link(si2);
2010 if (string_integer_fits_long(new_si))
2011 {
2012 long new_long = long_from_string_integer(new_si);
2013 cut_link(new_si);
2014 return i_integer(new_long);
2015 }
2016 return i_integer(new_si);
2017 }
2018 case IIT_STRING_INT:
2019 {
2020 string_integer *this_si =
2021 string_integer_from_long(value.long_val);
2022 string_integer *other_si = other.value.si_val;
2023 string_integer *new_si =
2024 bitwise_op_string_integers(this_si, other_si,
2025 BBO_XOR);
2026 cut_link(this_si);
2027 if (string_integer_fits_long(new_si))
2028 {
2029 long new_long = long_from_string_integer(new_si);
2030 cut_link(new_si);
2031 return i_integer(new_long);
2032 }
2033 return i_integer(new_si);
2034 }
2035 case IIT_POS_INFINITY:
2036 case IIT_NEG_INFINITY:
2037 case IIT_SIGNLESS_INFINITY:
2038 if (is_negative())
2039 return ~other;
2040 else
2041 return other;
2042 case IIT_UNDETERMINED:
2043 return i_integer();
2044 default:
2045 assert(FALSE);
2046 return i_integer();
2047 }
2048 case IIT_STRING_INT:
2049 switch (other.the_tag)
2050 {
2051 case IIT_C_INT:
2052 {
2053 string_integer *this_si = value.si_val;
2054 string_integer *other_si =
2055 string_integer_from_long(other.value.long_val);
2056 string_integer *new_si =
2057 bitwise_op_string_integers(this_si, other_si,
2058 BBO_XOR);
2059 cut_link(other_si);
2060 if (string_integer_fits_long(new_si))
2061 {
2062 long new_long = long_from_string_integer(new_si);
2063 cut_link(new_si);
2064 return i_integer(new_long);
2065 }
2066 return i_integer(new_si);
2067 }
2068 case IIT_STRING_INT:
2069 {
2070 string_integer *this_si = value.si_val;
2071 string_integer *other_si = other.value.si_val;
2072 string_integer *new_si =
2073 bitwise_op_string_integers(this_si, other_si,
2074 BBO_XOR);
2075 if (string_integer_fits_long(new_si))
2076 {
2077 long new_long = long_from_string_integer(new_si);
2078 cut_link(new_si);
2079 return i_integer(new_long);
2080 }
2081 return i_integer(new_si);
2082 }
2083 case IIT_POS_INFINITY:
2084 case IIT_NEG_INFINITY:
2085 case IIT_SIGNLESS_INFINITY:
2086 if (is_negative())
2087 return ~other;
2088 else
2089 return other;
2090 case IIT_UNDETERMINED:
2091 return i_integer();
2092 default:
2093 assert(FALSE);
2094 return i_integer();
2095 }
2096 case IIT_POS_INFINITY:
2097 case IIT_NEG_INFINITY:
2098 case IIT_SIGNLESS_INFINITY:
2099 switch (other.the_tag)
2100 {
2101 case IIT_C_INT:
2102 case IIT_STRING_INT:
2103 if (other.is_negative())
2104 return ~(*this);
2105 else
2106 return *this;
2107 case IIT_POS_INFINITY:
2108 case IIT_NEG_INFINITY:
2109 case IIT_SIGNLESS_INFINITY:
2110 return i_integer();
2111 case IIT_UNDETERMINED:
2112 return i_integer();
2113 default:
2114 assert(FALSE);
2115 return i_integer();
2116 }
2117 case IIT_UNDETERMINED:
2118 return i_integer();
2119 default:
2120 assert(FALSE);
2121 return i_integer();
2122 }
2123 }
2124
2125 i_integer i_integer::operator&(const i_integer &other) const
2126 {
2127 switch (the_tag)
2128 {
2129 case IIT_C_INT:
2130 switch (other.the_tag)
2131 {
2132 case IIT_C_INT:
2133 {
2134 long this_long = value.long_val;
2135 long other_long = other.value.long_val;
2136
2137 if ((this_long >= 0) && (other_long >= 0))
2138 {
2139 return i_integer(((unsigned long)this_long) &
2140 ((unsigned long)other_long));
2141 }
2142
2143 string_integer *si1 = string_integer_from_long(this_long);
2144 string_integer *si2 = string_integer_from_long(other_long);
2145 string_integer *new_si =
2146 bitwise_op_string_integers(si1, si2, BBO_AND);
2147 cut_link(si1);
2148 cut_link(si2);
2149 if (string_integer_fits_long(new_si))
2150 {
2151 long new_long = long_from_string_integer(new_si);
2152 cut_link(new_si);
2153 return i_integer(new_long);
2154 }
2155 return i_integer(new_si);
2156 }
2157 case IIT_STRING_INT:
2158 {
2159 string_integer *this_si =
2160 string_integer_from_long(value.long_val);
2161 string_integer *other_si = other.value.si_val;
2162 string_integer *new_si =
2163 bitwise_op_string_integers(this_si, other_si,
2164 BBO_AND);
2165 cut_link(this_si);
2166 if (string_integer_fits_long(new_si))
2167 {
2168 long new_long = long_from_string_integer(new_si);
2169 cut_link(new_si);
2170 return i_integer(new_long);
2171 }
2172 return i_integer(new_si);
2173 }
2174 case IIT_POS_INFINITY:
2175 case IIT_NEG_INFINITY:
2176 case IIT_SIGNLESS_INFINITY:
2177 if (is_negative())
2178 return other;
2179 else
2180 return i_integer();
2181 case IIT_UNDETERMINED:
2182 return i_integer();
2183 default:
2184 assert(FALSE);
2185 return i_integer();
2186 }
2187 case IIT_STRING_INT:
2188 switch (other.the_tag)
2189 {
2190 case IIT_C_INT:
2191 {
2192 string_integer *this_si = value.si_val;
2193 string_integer *other_si =
2194 string_integer_from_long(other.value.long_val);
2195 string_integer *new_si =
2196 bitwise_op_string_integers(this_si, other_si,
2197 BBO_AND);
2198 cut_link(other_si);
2199 if (string_integer_fits_long(new_si))
2200 {
2201 long new_long = long_from_string_integer(new_si);
2202 cut_link(new_si);
2203 return i_integer(new_long);
2204 }
2205 return i_integer(new_si);
2206 }
2207 case IIT_STRING_INT:
2208 {
2209 string_integer *this_si = value.si_val;
2210 string_integer *other_si = other.value.si_val;
2211 string_integer *new_si =
2212 bitwise_op_string_integers(this_si, other_si,
2213 BBO_AND);
2214 if (string_integer_fits_long(new_si))
2215 {
2216 long new_long = long_from_string_integer(new_si);
2217 cut_link(new_si);
2218 return i_integer(new_long);
2219 }
2220 return i_integer(new_si);
2221 }
2222 case IIT_POS_INFINITY:
2223 case IIT_NEG_INFINITY:
2224 case IIT_SIGNLESS_INFINITY:
2225 if (is_negative())
2226 return other;
2227 else
2228 return i_integer();
2229 case IIT_UNDETERMINED:
2230 return i_integer();
2231 default:
2232 assert(FALSE);
2233 return i_integer();
2234 }
2235 case IIT_POS_INFINITY:
2236 case IIT_NEG_INFINITY:
2237 case IIT_SIGNLESS_INFINITY:
2238 switch (other.the_tag)
2239 {
2240 case IIT_C_INT:
2241 case IIT_STRING_INT:
2242 if (other.is_negative())
2243 return *this;
2244 else
2245 return i_integer();
2246 case IIT_POS_INFINITY:
2247 case IIT_NEG_INFINITY:
2248 case IIT_SIGNLESS_INFINITY:
2249 return i_integer();
2250 case IIT_UNDETERMINED:
2251 return i_integer();
2252 default:
2253 assert(FALSE);
2254 return i_integer();
2255 }
2256 case IIT_UNDETERMINED:
2257 return i_integer();
2258 default:
2259 assert(FALSE);
2260 return i_integer();
2261 }
2262 }
2263
2264 i_integer i_integer::operator|(const i_integer &other) const
2265 {
2266 switch (the_tag)
2267 {
2268 case IIT_C_INT:
2269 switch (other.the_tag)
2270 {
2271 case IIT_C_INT:
2272 {
2273 long this_long = value.long_val;
2274 long other_long = other.value.long_val;
2275
2276 if ((this_long >= 0) && (other_long >= 0))
2277 {
2278 return i_integer(((unsigned long)this_long) |
2279 ((unsigned long)other_long));
2280 }
2281
2282 string_integer *si1 = string_integer_from_long(this_long);
2283 string_integer *si2 = string_integer_from_long(other_long);
2284 string_integer *new_si =
2285 bitwise_op_string_integers(si1, si2, BBO_IOR);
2286 cut_link(si1);
2287 cut_link(si2);
2288 if (string_integer_fits_long(new_si))
2289 {
2290 long new_long = long_from_string_integer(new_si);
2291 cut_link(new_si);
2292 return i_integer(new_long);
2293 }
2294 return i_integer(new_si);
2295 }
2296 case IIT_STRING_INT:
2297 {
2298 string_integer *this_si =
2299 string_integer_from_long(value.long_val);
2300 string_integer *other_si = other.value.si_val;
2301 string_integer *new_si =
2302 bitwise_op_string_integers(this_si, other_si,
2303 BBO_IOR);
2304 cut_link(this_si);
2305 if (string_integer_fits_long(new_si))
2306 {
2307 long new_long = long_from_string_integer(new_si);
2308 cut_link(new_si);
2309 return i_integer(new_long);
2310 }
2311 return i_integer(new_si);
2312 }
2313 case IIT_POS_INFINITY:
2314 case IIT_NEG_INFINITY:
2315 case IIT_SIGNLESS_INFINITY:
2316 if (is_negative())
2317 return i_integer();
2318 else
2319 return other;
2320 case IIT_UNDETERMINED:
2321 return i_integer();
2322 default:
2323 assert(FALSE);
2324 return i_integer();
2325 }
2326 case IIT_STRING_INT:
2327 switch (other.the_tag)
2328 {
2329 case IIT_C_INT:
2330 {
2331 string_integer *this_si = value.si_val;
2332 string_integer *other_si =
2333 string_integer_from_long(other.value.long_val);
2334 string_integer *new_si =
2335 bitwise_op_string_integers(this_si, other_si,
2336 BBO_IOR);
2337 cut_link(other_si);
2338 if (string_integer_fits_long(new_si))
2339 {
2340 long new_long = long_from_string_integer(new_si);
2341 cut_link(new_si);
2342 return i_integer(new_long);
2343 }
2344 return i_integer(new_si);
2345 }
2346 case IIT_STRING_INT:
2347 {
2348 string_integer *this_si = value.si_val;
2349 string_integer *other_si = other.value.si_val;
2350 string_integer *new_si =
2351 bitwise_op_string_integers(this_si, other_si,
2352 BBO_IOR);
2353 if (string_integer_fits_long(new_si))
2354 {
2355 long new_long = long_from_string_integer(new_si);
2356 cut_link(new_si);
2357 return i_integer(new_long);
2358 }
2359 return i_integer(new_si);
2360 }
2361 case IIT_POS_INFINITY:
2362 case IIT_NEG_INFINITY:
2363 case IIT_SIGNLESS_INFINITY:
2364 if (is_negative())
2365 return i_integer();
2366 else
2367 return other;
2368 case IIT_UNDETERMINED:
2369 return i_integer();
2370 default:
2371 assert(FALSE);
2372 return i_integer();
2373 }
2374 case IIT_POS_INFINITY:
2375 case IIT_NEG_INFINITY:
2376 case IIT_SIGNLESS_INFINITY:
2377 switch (other.the_tag)
2378 {
2379 case IIT_C_INT:
2380 case IIT_STRING_INT:
2381 if (other.is_negative())
2382 return i_integer();
2383 else
2384 return *this;
2385 case IIT_POS_INFINITY:
2386 case IIT_NEG_INFINITY:
2387 case IIT_SIGNLESS_INFINITY:
2388 return i_integer();
2389 case IIT_UNDETERMINED:
2390 return i_integer();
2391 default:
2392 assert(FALSE);
2393 return i_integer();
2394 }
2395 case IIT_UNDETERMINED:
2396 return i_integer();
2397 default:
2398 assert(FALSE);
2399 return i_integer();
2400 }
2401 }
2402
2403 i_integer i_integer::operator~(void) const
2404 {
2405 return -(add(1));
2406 }
2407
2408 i_integer i_integer::operator<<(const i_integer &other) const
2409 {
2410 return (*this >> -other);
2411 }
2412
2413 i_integer i_integer::operator>>(const i_integer &other) const
2414 {
2415 switch (the_tag)
2416 {
2417 case IIT_C_INT:
2418 switch (other.the_tag)
2419 {
2420 case IIT_C_INT:
2421 {
2422 long this_long = value.long_val;
2423 long other_long = other.value.long_val;
2424
2425 if (other_long == 0)
2426 {
2427 return *this;
2428 }
2429 else if (other_long > 0)
2430 {
2431 if (this_long < 0)
2432 return (~((~(*this)) >> other));
2433
2434 if (other_long <
2435 (long)(sizeof(unsigned long) * CHAR_BIT))
2436 {
2437 return i_integer(((unsigned long)this_long) >>
2438 other_long);
2439 }
2440 else
2441 {
2442 return 0;
2443 }
2444 }
2445 else
2446 {
2447 if ((this_long >= 0) &&
2448 (other_long >
2449 -(long)(sizeof(unsigned long) * CHAR_BIT)))
2450 {
2451 unsigned long this_ulong =
2452 (unsigned long)this_long;
2453 unsigned long result = (this_ulong << -other_long);
2454 if ((result >> -other_long) == this_ulong)
2455 return result;
2456 }
2457 }
2458
2459 string_integer *si1 = string_integer_from_long(this_long);
2460 string_integer *si2 = string_integer_from_long(other_long);
2461 string_integer *new_si =
2462 right_shift_string_integers(si1, si2);
2463 cut_link(si1);
2464 cut_link(si2);
2465 if (string_integer_fits_long(new_si))
2466 {
2467 long new_long = long_from_string_integer(new_si);
2468 cut_link(new_si);
2469 return i_integer(new_long);
2470 }
2471 return i_integer(new_si);
2472 }
2473 case IIT_STRING_INT:
2474 {
2475 string_integer *this_si =
2476 string_integer_from_long(value.long_val);
2477 string_integer *other_si = other.value.si_val;
2478 string_integer *new_si =
2479 right_shift_string_integers(this_si, other_si);
2480 cut_link(this_si);
2481 if (string_integer_fits_long(new_si))
2482 {
2483 long new_long = long_from_string_integer(new_si);
2484 cut_link(new_si);
2485 return i_integer(new_long);
2486 }
2487 return i_integer(new_si);
2488 }
2489 case IIT_POS_INFINITY:
2490 if (is_negative())
2491 return -1;
2492 else
2493 return 0;
2494 case IIT_NEG_INFINITY:
2495 if (value.long_val == 0)
2496 return 0;
2497 else if (is_negative())
2498 return other;
2499 else
2500 return -other;
2501 case IIT_SIGNLESS_INFINITY:
2502 return i_integer();
2503 case IIT_UNDETERMINED:
2504 return i_integer();
2505 default:
2506 assert(FALSE);
2507 return i_integer();
2508 }
2509 case IIT_STRING_INT:
2510 switch (other.the_tag)
2511 {
2512 case IIT_C_INT:
2513 {
2514 if (other.value.long_val == 0)
2515 return *this;
2516
2517 string_integer *this_si = value.si_val;
2518 string_integer *other_si =
2519 string_integer_from_long(other.value.long_val);
2520 string_integer *new_si =
2521 right_shift_string_integers(this_si, other_si);
2522 cut_link(other_si);
2523 if (string_integer_fits_long(new_si))
2524 {
2525 long new_long = long_from_string_integer(new_si);
2526 cut_link(new_si);
2527 return i_integer(new_long);
2528 }
2529 return i_integer(new_si);
2530 }
2531 case IIT_STRING_INT:
2532 {
2533 string_integer *this_si = value.si_val;
2534 string_integer *other_si = other.value.si_val;
2535 string_integer *new_si =
2536 right_shift_string_integers(this_si, other_si);
2537 if (string_integer_fits_long(new_si))
2538 {
2539 long new_long = long_from_string_integer(new_si);
2540 cut_link(new_si);
2541 return i_integer(new_long);
2542 }
2543 return i_integer(new_si);
2544 }
2545 case IIT_POS_INFINITY:
2546 if (is_negative())
2547 return -1;
2548 else
2549 return 0;
2550 case IIT_NEG_INFINITY:
2551 if (is_negative())
2552 return other;
2553 else
2554 return -other;
2555 case IIT_SIGNLESS_INFINITY:
2556 return i_integer();
2557 case IIT_UNDETERMINED:
2558 return i_integer();
2559 default:
2560 assert(FALSE);
2561 return i_integer();
2562 }
2563 case IIT_POS_INFINITY:
2564 case IIT_NEG_INFINITY:
2565 case IIT_SIGNLESS_INFINITY:
2566 switch (other.the_tag)
2567 {
2568 case IIT_C_INT:
2569 case IIT_STRING_INT:
2570 return *this;
2571 case IIT_POS_INFINITY:
2572 return i_integer();
2573 case IIT_NEG_INFINITY:
2574 return *this;
2575 case IIT_SIGNLESS_INFINITY:
2576 return i_integer();
2577 case IIT_UNDETERMINED:
2578 return i_integer();
2579 default:
2580 assert(FALSE);
2581 return i_integer();
2582 }
2583 case IIT_UNDETERMINED:
2584 return i_integer();
2585 default:
2586 assert(FALSE);
2587 return i_integer();
2588 }
2589 }
2590
2591
2592 void i_rational::reduce(void)
2593 {
2594 if (the_numerator.is_finite() && the_denominator.is_finite())
2595 {
2596 if (the_denominator == 0)
2597 {
2598 the_numerator = i_signless_infinity();
2599 the_denominator = 1;
2600 }
2601 else
2602 {
2603 boolean result_negative =
2604 (the_numerator.is_negative() !=
2605 the_numerator.is_negative());
2606 if (the_numerator.is_negative())
2607 the_numerator = -the_numerator;
2608 if (the_denominator.is_negative())
2609 the_denominator = -the_denominator;
2610 i_integer the_gcd = ii_gcd(the_numerator, the_denominator);
2611 the_numerator /= the_gcd;
2612 the_denominator /= the_gcd;
2613 if (result_negative)
2614 the_numerator = -the_numerator;
2615 }
2616 }
2617 else
2618 {
2619 if (the_numerator.is_undetermined() ||
2620 the_denominator.is_undetermined())
2621 {
2622 the_denominator = 1;
2623 }
2624 else if (the_numerator.is_finite())
2625 {
2626 the_numerator = 0;
2627 the_denominator = 1;
2628 }
2629 else if (the_denominator.is_finite())
2630 {
2631 if (the_denominator == 0)
2632 {
2633 the_numerator = i_integer();
2634 the_denominator = 1;
2635 }
2636 else if (the_denominator.is_negative())
2637 {
2638 the_numerator = -the_numerator;
2639 the_denominator = 1;
2640 }
2641 else
2642 {
2643 the_denominator = 1;
2644 }
2645 }
2646 else
2647 {
2648 the_numerator = i_integer();
2649 the_denominator = 1;
2650 }
2651 }
2652 }
2653
2654 i_integer i_rational::written_length(int base) const
2655 {
2656 if (the_denominator == 1)
2657 {
2658 return the_numerator.written_length(base);
2659 }
2660 else
2661 {
2662 return the_numerator.written_length(base) +
2663 the_denominator.written_length(base) + 1;
2664 }
2665 }
2666
2667 void i_rational::write(char *location, int base) const
2668 {
2669 the_numerator.write(location, base);
2670 if (the_denominator != 1)
2671 {
2672 unsigned long denominator_length = strlen(location);
2673 location[denominator_length] = '/';
2674 the_denominator.write(&(location[denominator_length + 1]), base);
2675 }
2676 }
2677
2678 void i_rational::read(const char *location, int base)
2679 {
2680 const char *follow_string = location;
2681
2682 i_rational new_numerator =
2683 read_digits_with_decimal_point(&follow_string, base);
2684
2685 while (isspace(*follow_string))
2686 ++follow_string;
2687
2688 if (*follow_string == '/')
2689 {
2690 ++follow_string;
2691 i_rational new_denominator =
2692 read_digits_with_decimal_point(&follow_string, base);
2693 operator=(new_numerator / new_denominator);
2694 }
2695 else
2696 {
2697 operator=(new_numerator);
2698 }
2699 }
2700
2701 void i_rational::print(FILE *fp, int base) const
2702 {
2703 the_numerator.print(fp, base);
2704 if (the_denominator != 1)
2705 {
2706 fputc('/', fp);
2707 the_denominator.print(fp, base);
2708 }
2709 }
2710
2711 i_integer i_rational::floor(void) const
2712 {
2713 i_integer div = the_numerator / the_denominator;
2714 i_integer mod = the_numerator % the_denominator;
2715 if (mod < 0)
2716 return div - 1;
2717 else
2718 return div;
2719 }
2720
2721 i_integer i_rational::ceiling(void) const
2722 {
2723 return -((-(*this)).floor());
2724 }
2725
2726 i_integer i_rational::round(void) const
2727 {
2728 return (*this + i_rational(1, 2)).floor();
2729 }
2730
2731 /*----------------------------------------------------------------------*
2732 End Public Method Implementations
2733 *----------------------------------------------------------------------*/
2734 /*----------------------------------------------------------------------*
2735 Begin Public Function Implementations
2736 *----------------------------------------------------------------------*/
2737
2738 extern i_integer i_positive_infinity(void)
2739 {
2740 i_integer result;
2741 result.the_tag = IIT_POS_INFINITY;
2742 return result;
2743 }
2744
2745 extern i_integer i_negative_infinity(void)
2746 {
2747 i_integer result;
2748 result.the_tag = IIT_NEG_INFINITY;
2749 return result;
2750 }
2751
2752 extern i_integer i_signless_infinity(void)
2753 {
2754 i_integer result;
2755 result.the_tag = IIT_SIGNLESS_INFINITY;
2756 return result;
2757 }
2758
2759 extern i_integer ii_gcd(const i_integer &op1, const i_integer &op2)
2760 {
2761 i_integer a = op1;
2762 i_integer b = op2;
2763
2764 if (a < 0)
2765 a = -a;
2766 if (b < 0)
2767 b = -b;
2768
2769 if (a < b)
2770 {
2771 i_integer temp_ii = a;
2772 a = b;
2773 b = temp_ii;
2774 }
2775
2776 while (TRUE)
2777 {
2778 if (b == 0)
2779 return a;
2780
2781 if (b == 1)
2782 return 1;
2783
2784 i_integer new_a = b;
2785 b = a % b;
2786 a = new_a;
2787 }
2788 }
2789
2790 extern i_integer ii_gcd(const i_integer &op1, const i_integer &op2,
2791 i_integer *coeff1, i_integer *coeff2)
2792 {
2793 i_integer a = op1;
2794 i_integer b = op2;
2795
2796 i_integer n = 1;
2797 i_integer p = 0;
2798
2799 if (a < 0)
2800 {
2801 a = -a;
2802 n = -1;
2803 }
2804 if (b < 0)
2805 b = -b;
2806
2807 if (a < b)
2808 {
2809 i_integer temp_ii = a;
2810 a = b;
2811 b = temp_ii;
2812
2813 p = n;
2814 n = 0;
2815 }
2816
2817 while (TRUE)
2818 {
2819 /*
2820 * Invariant conditions:
2821 * op1 * n + op2 * m = a
2822 * op1 * p + op2 * q = b
2823 * where all variables are integers, op1 and op2 never change.
2824 *
2825 * The values of a and b on the next iteration:
2826 * new_a = b
2827 * new_b = a % b
2828 *
2829 * Which means that if we let:
2830 * new_n = p
2831 * new_m = q
2832 * new_p = n - p * (a div b)
2833 * new_q = m - q * (a div b)
2834 *
2835 * Note that there is a recurrence between n and p, and one
2836 * between m and q, and both depend on the values of a and b
2837 * at each iteration. But it is not necessary to keep track
2838 * of q and m to calculate n and p (or equivalently, it would
2839 * not be necessary to keep track of n and p to calculate q
2840 * and m). Since we can derive m and q from the other
2841 * values, it is not necessary to calculate them at every
2842 * stage. So here we keep track of just n and p, and at the
2843 * end, when we want n and m, we have n and just derive m to
2844 * write into *coeff1 and *coeff2.
2845 */
2846 if (b == 0)
2847 {
2848 *coeff1 = n;
2849 *coeff2 = (a - (op1 * n)) / op2;
2850 return a;
2851 }
2852
2853 if (b == 1)
2854 {
2855 *coeff1 = p;
2856 *coeff2 = (i_integer(1) - (op1 * p)) / op2;
2857 return 1;
2858 }
2859
2860 i_integer new_n = p;
2861 p = n - (p * (a / b));
2862 n = new_n;
2863
2864 i_integer new_a = b;
2865 b = a % b;
2866 a = new_a;
2867 }
2868 }
2869
2870 /*----------------------------------------------------------------------*
2871 End Public Function Implementations
2872 *----------------------------------------------------------------------*/
2873 /*----------------------------------------------------------------------*
2874 Begin Private Function Implementations
2875 *----------------------------------------------------------------------*/
2876
2877 static void add_link(string_integer *the_si)
2878 {
2879 if (the_si->link_count < ULONG_MAX)
2880 ++the_si->link_count;
2881 }
2882
2883 static void cut_link(string_integer *the_si)
2884 {
2885 if (the_si->link_count < ULONG_MAX)
2886 --the_si->link_count;
2887 if (the_si->link_count == 0)
2888 delete the_si;
2889 }
2890
2891 static string_integer *add_string_integers(string_integer *op1,
2892 string_integer *op2)
2893 {
2894 char *this_digits = op1->the_digits;
2895 char *other_digits = op2->the_digits;
2896 unsigned long this_count = strlen(this_digits);
2897 unsigned long other_count = strlen(other_digits);
2898
2899 boolean reversed = FALSE;
2900
2901 if (string_magnitude_is_less(this_digits, other_digits, this_count,
2902 other_count, '0'))
2903 {
2904 reversed = TRUE;
2905 char *temp_ptr = this_digits;
2906 this_digits = other_digits;
2907 other_digits = temp_ptr;
2908 unsigned long temp_count = this_count;
2909 this_count = other_count;
2910 other_count = temp_count;
2911 }
2912
2913 if (op1->is_negative != op2->is_negative)
2914 {
2915 string_integer *new_si = new string_integer(this_count);
2916 if (reversed)
2917 new_si->is_negative = op2->is_negative;
2918 else
2919 new_si->is_negative = op1->is_negative;
2920 subtract_string_magnitudes(new_si->the_digits, this_digits,
2921 other_digits, this_count, other_count, 10,
2922 '0');
2923 justify_int_string(new_si->the_digits, this_count, '0');
2924 if (new_si->the_digits[0] == 0)
2925 new_si->is_negative = FALSE;
2926 return new_si;
2927 }
2928 else
2929 {
2930 string_integer *new_si = new string_integer(this_count + 1);
2931 new_si->is_negative = op1->is_negative;
2932 add_string_magnitudes(new_si->the_digits, this_digits, other_digits,
2933 this_count, other_count, 10, '0');
2934
2935 if (*(new_si->the_digits) == '0')
2936 {
2937 memmove(new_si->the_digits, &(new_si->the_digits[1]), this_count);
2938 new_si->the_digits[this_count] = 0;
2939 }
2940 else
2941 {
2942 new_si->the_digits[this_count + 1] = 0;
2943 }
2944 return new_si;
2945 }
2946 }
2947
2948 static string_integer *multiply_string_integers(string_integer *op1,
2949 string_integer *op2)
2950 {
2951 static unsigned long scratch_size = 0;
2952 static char *scratch_buffer = NULL;
2953
2954 char *this_digits = op1->the_digits;
2955 char *other_digits = op2->the_digits;
2956 unsigned long this_count = strlen(this_digits);
2957 unsigned long other_count = strlen(other_digits);
2958
2959 if (this_count < other_count)
2960 {
2961 char *temp_ptr = this_digits;
2962 this_digits = other_digits;
2963 other_digits = temp_ptr;
2964 unsigned long temp_count = this_count;
2965 this_count = other_count;
2966 other_count = temp_count;
2967 }
2968
2969 if (this_count > ULONG_MAX - other_count)
2970 error_line(1, NULL, "out of memory address space");
2971 unsigned long new_count = this_count + other_count;
2972
2973 if (9 * new_count > scratch_size)
2974 {
2975 if (scratch_buffer != NULL)
2976 delete[] scratch_buffer;
2977 scratch_buffer = new char[9 * new_count];
2978 scratch_size = 9 * new_count;
2979 }
2980
2981 string_integer *new_si = new string_integer(new_count);
2982 new_si->is_negative = (op1->is_negative != op2->is_negative);
2983 multiply_string_magnitudes(new_si->the_digits, scratch_buffer, this_digits,
2984 other_digits, this_count, other_count, 10, '0');
2985 justify_int_string(new_si->the_digits, new_count, '0');
2986 return new_si;
2987 }
2988
2989 static string_integer *div_string_integers(string_integer *op1,
2990 string_integer *op2)
2991 {
2992 static unsigned long scratch_size = 0;
2993 static char *scratch_buffer = NULL;
2994
2995 char *this_digits = op1->the_digits;
2996 char *other_digits = op2->the_digits;
2997 unsigned long this_count = strlen(this_digits);
2998 unsigned long other_count = strlen(other_digits);
2999
3000 if (this_count < other_count)
3001 return new string_integer(0);
3002
3003 if (other_count > scratch_size)
3004 {
3005 if (scratch_buffer != NULL)
3006 delete[] scratch_buffer;
3007 scratch_buffer = new char[other_count];
3008 scratch_size = other_count;
3009 }
3010
3011 string_integer *new_si =
3012 new string_integer((this_count - other_count) + 1);
3013 new_si->is_negative = (op1->is_negative != op2->is_negative);
3014 divide_string_magnitudes(new_si->the_digits, scratch_buffer, this_digits,
3015 other_digits, this_count, other_count, '0');
3016 justify_int_string(new_si->the_digits, (this_count - other_count) + 1,
3017 '0');
3018 return new_si;
3019 }
3020
3021 static string_integer *mod_string_integers(string_integer *op1,
3022 string_integer *op2)
3023 {
3024 static unsigned long scratch_size = 0;
3025 static char *scratch_buffer = NULL;
3026
3027 char *this_digits = op1->the_digits;
3028 char *other_digits = op2->the_digits;
3029 unsigned long this_count = strlen(this_digits);
3030 unsigned long other_count = strlen(other_digits);
3031
3032 if (this_count < other_count)
3033 {
3034 add_link(op1);
3035 return op1;
3036 }
3037
3038 if ((this_count - other_count) + 1 > scratch_size)
3039 {
3040 if (scratch_buffer != NULL)
3041 delete[] scratch_buffer;
3042 scratch_size = (this_count - other_count) + 1;
3043 scratch_buffer = new char[scratch_size];
3044 }
3045
3046 string_integer *new_si = new string_integer(other_count);
3047 new_si->is_negative = op1->is_negative;
3048 divide_string_magnitudes(scratch_buffer, new_si->the_digits, this_digits,
3049 other_digits, this_count, other_count, '0');
3050 justify_int_string(new_si->the_digits, other_count, '0');
3051 return new_si;
3052 }
3053
3054 static string_integer *bitwise_op_string_integers(string_integer *op1,
3055 string_integer *op2,
3056 binary_bit_ops op)
3057 {
3058 unsigned char *bits1;
3059 unsigned char *bits2;
3060 unsigned long size1;
3061 unsigned long size2;
3062 int carry1;
3063 int carry2;
3064
3065 string_integer_to_binary(&bits1, &size1, &carry1, op1);
3066 string_integer_to_binary(&bits2, &size2, &carry2, op2);
3067
3068 if (size1 < size2)
3069 {
3070 unsigned char *temp_bits = bits1;
3071 bits1 = bits2;
3072 bits2 = temp_bits;
3073 unsigned long temp_size = size1;
3074 size1 = size2;
3075 size2 = temp_size;
3076 int temp_carry = carry1;
3077 carry1 = carry2;
3078 carry2 = temp_carry;
3079 }
3080
3081 unsigned char *follow1 = &(bits1[size1 - 1]);
3082 unsigned char *follow2 = &(bits2[size2 - 1]);
3083
3084 switch (op)
3085 {
3086 case BBO_XOR:
3087 while (TRUE)
3088 {
3089 *follow1 = *follow1 ^ *follow2;
3090 if (follow2 == bits2)
3091 break;
3092 --follow1;
3093 --follow2;
3094 }
3095 break;
3096 case BBO_AND:
3097 while (TRUE)
3098 {
3099 *follow1 = *follow1 & *follow2;
3100 if (follow2 == bits2)
3101 break;
3102 --follow1;
3103 --follow2;
3104 }
3105 break;
3106 case BBO_IOR:
3107 while (TRUE)
3108 {
3109 *follow1 = *follow1 | *follow2;
3110 if (follow2 == bits2)
3111 break;
3112 --follow1;
3113 --follow2;
3114 }
3115 break;
3116 default:
3117 assert(FALSE);
3118 }
3119 assert(follow1 >= bits1);
3120
3121 if (carry2 == 1)
3122 {
3123 if (op == BBO_AND)
3124 follow1 = bits1;
3125 else
3126 carry1 = 1;
3127 }
3128 else
3129 {
3130 if (op == BBO_AND)
3131 carry1 = 0;
3132 else
3133 follow1 = bits1;
3134 }
3135
3136 string_integer *result =
3137 binary_to_string_integer(follow1,
3138 (&(bits1[size1 - 1]) - follow1) + 1,
3139 carry1);
3140 delete[] bits1;
3141 delete[] bits2;
3142 return result;
3143 }
3144
3145 static string_integer *right_shift_string_integers(string_integer *op1,
3146 string_integer *op2)
3147 {
3148 unsigned char *bits;
3149 unsigned long bit_size;
3150 int carry;
3151
3152 string_integer_to_binary(&bits, &bit_size, &carry, op1);
3153
3154 long right_amount;
3155 if (op2->is_negative)
3156 {
3157 char *old_digits = op2->the_digits;
3158 string_integer *left_si = new string_integer(strlen(old_digits));
3159 strcpy(left_si->the_digits, old_digits);
3160 left_si->is_negative = FALSE;
3161
3162 string_integer *eight_si = string_integer_from_long(8);
3163 string_integer *div_si = div_string_integers(left_si, eight_si);
3164 string_integer *mod_si = mod_string_integers(left_si, eight_si);
3165 cut_link(left_si);
3166 cut_link(eight_si);
3167
3168 assert(string_integer_fits_long(mod_si));
3169 long mod_long = long_from_string_integer(mod_si);
3170 cut_link(mod_si);
3171 assert((mod_long < 8) && (mod_long >= 0));
3172 right_amount = ((mod_long == 0) ? 0 : 8 - mod_long);
3173
3174 if (!string_integer_fits_long(div_si))
3175 error_line(1, NULL, "out of memory address space");
3176 long add_digits = long_from_string_integer(div_si);
3177 cut_link(div_si);
3178
3179 if (mod_long != 0)
3180 {
3181 if (add_digits == LONG_MAX)
3182 error_line(1, NULL, "out of memory address space");
3183 ++add_digits;
3184 }
3185
3186 assert(add_digits > 0);
3187 unsigned long ulong_add = add_digits;
3188 if (bit_size > LONG_MAX - ulong_add)
3189 error_line(1, NULL, "out of memory address space");
3190 unsigned char *new_bits = new unsigned char[bit_size + ulong_add];
3191 strncpy((char *)new_bits, (char *)bits, bit_size);
3192 memset(&(new_bits[bit_size]), 0, ulong_add);
3193 delete[] bits;
3194 bits = new_bits;
3195 bit_size += ulong_add;
3196 }
3197 else
3198 {
3199 string_integer *eight_si = string_integer_from_long(8);
3200 string_integer *div_si = div_string_integers(op2, eight_si);
3201 string_integer *mod_si = mod_string_integers(op2, eight_si);
3202 cut_link(eight_si);
3203
3204 assert(string_integer_fits_long(mod_si));
3205 right_amount = long_from_string_integer(mod_si);
3206 cut_link(mod_si);
3207
3208 if (!string_integer_fits_long(div_si))
3209 {
3210 cut_link(div_si);
3211 return string_integer_from_long((carry == 1) ? -1 : 0);
3212 }
3213 long cut_digits = long_from_string_integer(div_si);
3214 cut_link(div_si);
3215
3216 assert(cut_digits >= 0);
3217 if (((unsigned long)cut_digits) >= bit_size)
3218 return string_integer_from_long((carry == 1) ? -1 : 0);
3219 bit_size -= cut_digits;
3220 }
3221 assert((right_amount >= 0) && (right_amount < 8));
3222
3223 if (right_amount != 0)
3224 {
3225 unsigned char *follow_bits = bits;
3226 unsigned char *bit_end = &(bits[bit_size - 1]);
3227 unsigned char mask = ~((~((unsigned)0)) << right_amount);
3228 unsigned char temp_byte = ((carry == 1) ? mask : 0);
3229 while (TRUE)
3230 {
3231 unsigned char old_byte = *follow_bits;
3232 *follow_bits =
3233 (old_byte >> right_amount) |
3234 (temp_byte << (8 - right_amount));
3235 temp_byte = old_byte & mask;
3236 if (follow_bits == bit_end)
3237 break;
3238 ++follow_bits;
3239 }
3240 }
3241
3242 string_integer *result = binary_to_string_integer(bits, bit_size, carry);
3243 delete[] bits;
3244 return result;
3245 }
3246
3247 static boolean string_integer_fits_long(string_integer *the_si)
3248 {
3249 long long_total = 0;
3250
3251 char *digit_follow = the_si->the_digits;
3252 if (the_si->is_negative)
3253 {
3254 while (*digit_follow != 0)
3255 {
3256 long this_digit = *digit_follow - '0';
3257 if (long_total <
3258 (((LONG_MIN + this_digit) / 10) +
3259 ((((LONG_MIN + this_digit) % 10) > 0) ? 1 : 0)))
3260 {
3261 return FALSE;
3262 }
3263 long_total *= 10;
3264 long_total -= this_digit;
3265 ++digit_follow;
3266 }
3267 }
3268 else
3269 {
3270 while (*digit_follow != 0)
3271 {
3272 long this_digit = *digit_follow - '0';
3273 if (long_total > ((LONG_MAX - this_digit) / 10))
3274 return FALSE;
3275 long_total *= 10;
3276 long_total += this_digit;
3277 ++digit_follow;
3278 }
3279 }
3280 return TRUE;
3281 }
3282
3283 static long long_from_string_integer(string_integer *the_si)
3284 {
3285 long long_total = 0;
3286
3287 char *digit_follow = the_si->the_digits;
3288 if (the_si->is_negative)
3289 {
3290 while (*digit_follow != 0)
3291 {
3292 long this_digit = *digit_follow - '0';
3293 assert(long_total >=
3294 (((LONG_MIN + this_digit) / 10) +
3295 ((((LONG_MIN + this_digit) % 10) > 0) ? 1 : 0)));
3296 long_total *= 10;
3297 long_total -= this_digit;
3298 ++digit_follow;
3299 }
3300 }
3301 else
3302 {
3303 while (*digit_follow != 0)
3304 {
3305 long this_digit = *digit_follow - '0';
3306 assert(long_total <= ((LONG_MAX - this_digit) / 10));
3307 long_total *= 10;
3308 long_total += this_digit;
3309 ++digit_follow;
3310 }
3311 }
3312 return long_total;
3313 }
3314
3315 static string_integer *string_integer_from_long(long the_long)
3316 {
3317 static char buffer[sizeof(unsigned long) * CHAR_BIT / 3 + 2];
3318
3319 char *digit_follow = buffer;
3320 long remainder = the_long;
3321 if (the_long < 0)
3322 {
3323 while (remainder < 0)
3324 {
3325 long this_digit = remainder % 10;
3326 remainder /= 10;
3327 if (this_digit > 0)
3328 {
3329 this_digit -= 10;
3330 ++remainder;
3331 }
3332 *digit_follow = ((char)(-this_digit)) + '0';
3333 ++digit_follow;
3334 }
3335 }
3336 else
3337 {
3338 while (remainder > 0)
3339 {
3340 *digit_follow = ((char)(remainder % 10)) + '0';
3341 remainder /= 10;
3342 ++digit_follow;
3343 }
3344 }
3345
3346 unsigned long digits = digit_follow - buffer;
3347
3348 string_integer *new_si = new string_integer(digits);
3349 new_si->is_negative = (the_long < 0);
3350
3351 char *follow_back = new_si->the_digits;
3352 while (digit_follow != buffer)
3353 {
3354 --digit_follow;
3355 *follow_back = *digit_follow;
3356 ++follow_back;
3357 }
3358 assert(follow_back == &(new_si->the_digits[digits]));
3359 *follow_back = 0;
3360 return new_si;
3361 }
3362
3363 static string_integer *string_integer_from_unsigned_long(
3364 unsigned long the_ulong)
3365 {
3366 static char buffer[sizeof(unsigned long) * CHAR_BIT / 3 + 2];
3367
3368 char *digit_follow = buffer;
3369 unsigned long remainder = the_ulong;
3370 while (remainder > 0)
3371 {
3372 *digit_follow = ((char)(remainder % 10)) + '0';
3373 remainder /= 10;
3374 ++digit_follow;
3375 }
3376
3377 unsigned long digits = digit_follow - buffer;
3378
3379 string_integer *new_si = new string_integer(digits);
3380 new_si->is_negative = FALSE;
3381
3382 char *follow_back = new_si->the_digits;
3383 while (digit_follow != buffer)
3384 {
3385 --digit_follow;
3386 *follow_back = *digit_follow;
3387 ++follow_back;
3388 }
3389 assert(follow_back == &(new_si->the_digits[digits]));
3390 *follow_back = 0;
3391 return new_si;
3392 }
3393
3394 static void string_integer_to_binary(unsigned char **result,
3395 unsigned long *result_size,
3396 int *carry_bit,
3397 string_integer *the_si)
3398 {
3399 static char *buffer = NULL;
3400 static unsigned long buf_size = 0;
3401
3402 string_integer *this_si = the_si;
3403 add_link(this_si);
3404
3405 if (the_si->is_negative)
3406 {
3407 string_integer *one_si = new string_integer(1);
3408 one_si->is_negative = FALSE;
3409 one_si->the_digits[0] = '1';
3410 one_si->the_digits[1] = 0;
3411 string_integer *sum_si = add_string_integers(this_si, one_si);
3412 cut_link(this_si);
3413 cut_link(one_si);
3414 this_si = sum_si;
3415 }
3416
3417 char *this_digits = this_si->the_digits;
3418 unsigned long this_size = strlen(this_digits);
3419
3420 *carry_bit = (the_si->is_negative ? 1 : 0);
3421
3422 if (this_size == 0)
3423 {
3424 unsigned char *bits = new unsigned char[1];
3425 if (the_si->is_negative)
3426 bits[0] = ~0;
3427 else
3428 bits[0] = 0;
3429 *result = bits;
3430 *result_size = 1;
3431 cut_link(this_si);
3432 return;
3433 }
3434
3435 if ((buffer == NULL) || (buf_size < this_size * 20))
3436 {
3437 if (buffer != NULL)
3438 delete[] buffer;
3439 buf_size = this_size * 20;
3440 buffer = new char[buf_size];
3441 }
3442
3443 base_convert(buffer, &(buffer[this_size]), this_digits, this_size, 10,
3444 16, '0', 0);
3445
3446 char *follow_buffer = buffer;
3447 char *end_buffer = &(buffer[this_size - 1]);
3448 while ((*follow_buffer == 0) && (follow_buffer < end_buffer))
3449 ++follow_buffer;
3450
3451 unsigned long final_size = (end_buffer - follow_buffer) / 2 + 1;
3452 *result_size = final_size;
3453 unsigned char *bits = new unsigned char[final_size];
3454 *result = bits;
3455 unsigned char *follow_bits = bits;
3456 if (the_si->is_negative)
3457 {
3458 if ((end_buffer - follow_buffer) % 2 == 0)
3459 {
3460 unsigned char digit = *follow_buffer;
3461 *follow_bits = ~digit;
3462 if (follow_buffer < end_buffer)
3463 {
3464 ++follow_bits;
3465 ++follow_buffer;
3466 }
3467 }
3468 if (follow_buffer < end_buffer)
3469 {
3470 while (TRUE)
3471 {
3472 unsigned char digit1 = *follow_buffer;
3473 ++follow_buffer;
3474 unsigned char digit2 = *follow_buffer;
3475 *follow_bits = ~((digit1 << 4) | digit2);
3476 if (follow_buffer == end_buffer)
3477 break;
3478 ++follow_bits;
3479 ++follow_buffer;
3480 }
3481 }
3482 }
3483 else
3484 {
3485 if ((end_buffer - follow_buffer) % 2 == 0)
3486 {
3487 unsigned char digit = *follow_buffer;
3488 *follow_bits = digit;
3489 if (follow_buffer < end_buffer)
3490 {
3491 ++follow_bits;
3492 ++follow_buffer;
3493 }
3494 }
3495 if (follow_buffer < end_buffer)
3496 {
3497 while (TRUE)
3498 {
3499 unsigned char digit1 = *follow_buffer;
3500 ++follow_buffer;
3501 unsigned char digit2 = *follow_buffer;
3502 *follow_bits = ((digit1 << 4) | digit2);
3503 if (follow_buffer == end_buffer)
3504 break;
3505 ++follow_bits;
3506 ++follow_buffer;
3507 }
3508 }
3509 }
3510 assert(follow_bits == &(bits[final_size - 1]));
3511 cut_link(this_si);
3512 }
3513
3514 static string_integer *binary_to_string_integer(unsigned char *bits,
3515 unsigned long bit_size,
3516 int carry_bit)
3517 {
3518 assert(bit_size > 0);
3519
3520 static char *buffer = NULL;
3521 static unsigned long buf_size = 0;
3522
3523 if ((buffer == NULL) || (buf_size < bit_size * 20))
3524 {
3525 if (buffer != NULL)
3526 delete[] buffer;
3527 buf_size = bit_size * 20;
3528 buffer = new char[buf_size];
3529 }
3530
3531 unsigned char *bit_follow = bits;
3532 unsigned char *bit_end = &(bits[bit_size - 1]);
3533 char *buf_follow = buffer;
3534 if (carry_bit == 1)
3535 {
3536 while (TRUE)
3537 {
3538 unsigned char this_char = *bit_follow;
3539 *buf_follow = (~(this_char >> 4)) & 0xf;
3540 ++buf_follow;
3541 *buf_follow = ((~this_char) & 0xf);
3542 if (bit_follow == bit_end)
3543 break;
3544 ++bit_follow;
3545 ++buf_follow;
3546 }
3547 }
3548 else
3549 {
3550 while (TRUE)
3551 {
3552 unsigned char this_char = *bit_follow;
3553 *buf_follow = (this_char >> 4);
3554 ++buf_follow;
3555 *buf_follow = (this_char & 0xf);
3556 if (bit_follow == bit_end)
3557 break;
3558 ++bit_follow;
3559 ++buf_follow;
3560 }
3561 }
3562 assert(buf_follow == &(buffer[bit_size * 2 - 1]));
3563
3564 string_integer *new_si = new string_integer(bit_size * 4);
3565 new_si->is_negative = (carry_bit == 1);
3566 base_convert(new_si->the_digits, &(buffer[bit_size * 2]), buffer,
3567 bit_size * 2, 16, 10, 0, '0');
3568 justify_int_string(new_si->the_digits, bit_size * 4, '0');
3569 if (carry_bit == 1)
3570 {
3571 string_integer *neg_one_si = new string_integer(1);
3572 neg_one_si->is_negative = TRUE;
3573 neg_one_si->the_digits[0] = '1';
3574 neg_one_si->the_digits[1] = 0;
3575 string_integer *sum_si = add_string_integers(new_si, neg_one_si);
3576 cut_link(new_si);
3577 cut_link(neg_one_si);
3578 return sum_si;
3579 }
3580 return new_si;
3581 }
3582
3583 static boolean string_magnitude_is_less(char *op1, char *op2,
3584 unsigned long op1_len,
3585 unsigned long op2_len, int offset)
3586 {
3587 char *new_op1 = op1;
3588 char *new_op2 = op2;
3589 unsigned long new_op1_len = op1_len;
3590 unsigned long new_op2_len = op2_len;
3591
3592 while ((new_op1_len > 0) && (*new_op1 == offset))
3593 {
3594 --new_op1_len;
3595 ++new_op1;
3596 }
3597
3598 while ((new_op2_len > 0) && (*new_op2 == offset))
3599 {
3600 --new_op2_len;
3601 ++new_op2;
3602 }
3603
3604 if (new_op1_len < new_op2_len)
3605 return TRUE;
3606 if (new_op1_len > new_op2_len)
3607 return FALSE;
3608 return (strncmp(new_op1, new_op2, new_op1_len) < 0);
3609 }
3610
3611 /* This assumes that op1_len >= op2_len. The result will have length
3612 * op1_len + 1. */
3613 static void add_string_magnitudes(char *result, char *op1, char *op2,
3614 unsigned long op1_len,
3615 unsigned long op2_len, int base, int offset)
3616 {
3617 assert((base >= 2) && (base - 1 <= CHAR_MAX - offset) &&
3618 (base <= INT_MAX / 2));
3619
3620 char *sum_follow = &(result[op1_len + 1]);
3621 char *op1_follow = &(op1[op1_len]);
3622 char *op2_follow = &(op2[op2_len]);
3623
3624 int remainder = 0;
3625 while (op2_follow != op2)
3626 {
3627 --op1_follow;
3628 --op2_follow;
3629 --sum_follow;
3630 remainder += (*op1_follow - offset) + (*op2_follow - offset);
3631 *sum_follow = (remainder % base) + offset;
3632 remainder /= base;
3633 }
3634
3635 while ((op1_follow != op1) && (remainder != 0))
3636 {
3637 --op1_follow;
3638 --sum_follow;
3639 remainder += (*op1_follow - offset);
3640 *sum_follow = (remainder % base) + offset;
3641 remainder /= base;
3642 }
3643
3644 while (op1_follow != op1)
3645 {
3646 --op1_follow;
3647 --sum_follow;
3648 *sum_follow = *op1_follow;
3649 }
3650
3651 assert(sum_follow == &(result[1]));
3652 assert((remainder == 0) || (remainder == 1));
3653 *result = remainder + offset;
3654 }
3655
3656 /* assumes that adding op2 will not result in overflow */
3657 static void add_to_string_magnitude(char *result, char *op2,
3658 unsigned long result_len,
3659 unsigned long op2_len, int base,
3660 int offset)
3661 {
3662 assert((base >= 2) && (base - 1 <= CHAR_MAX - offset) &&
3663 (base <= INT_MAX / 2));
3664
3665 char *sum_follow = &(result[result_len]);
3666 char *op2_follow = &(op2[op2_len]);
3667
3668 char *op2_target = op2;
3669 while (((unsigned long)(op2_follow - op2_target)) > result_len)
3670 {
3671 assert(*op2_target == offset);
3672 ++op2_target;
3673 }
3674
3675 int remainder = 0;
3676 while (op2_follow != op2_target)
3677 {
3678 --op2_follow;
3679 --sum_follow;
3680 remainder += (*sum_follow - offset) + (*op2_follow - offset);
3681 *sum_follow = (remainder % base) + offset;
3682 remainder /= base;
3683 }
3684
3685 while (remainder != 0)
3686 {
3687 assert(sum_follow != result);
3688 --sum_follow;
3689 remainder += (*sum_follow - offset);
3690 *sum_follow = (remainder % base) + offset;
3691 remainder /= base;
3692 }
3693 }
3694
3695 /* This assumes that op1 >= op2. The result will have length op1_len.
3696 */
3697 static void subtract_string_magnitudes(char *result, char *op1, char *op2,
3698 unsigned long op1_len,
3699 unsigned long op2_len, int base,
3700 int offset)
3701 {
3702 assert((base >= 2) && (base - 1 <= CHAR_MAX - offset));
3703 if (INT_MAX + INT_MIN > 0)
3704 assert(base <= NEG_INT_MIN);
3705 else if (INT_MAX + INT_MIN < 0)
3706 assert(-base >= INT_MIN);
3707
3708 char *sum_follow = &(result[op1_len]);
3709 char *op1_follow = &(op1[op1_len]);
3710 char *op2_follow = &(op2[op2_len]);
3711 assert(op1_len >= op2_len);
3712
3713 int remainder = 0;
3714 while (op2_follow != op2)
3715 {
3716 --op1_follow;
3717 --op2_follow;
3718 --sum_follow;
3719 remainder += (*op1_follow - offset) - (*op2_follow - offset);
3720 if (remainder < 0)
3721 {
3722 *sum_follow = (remainder + base) + offset;
3723 remainder = -1;
3724 }
3725 else
3726 {
3727 *sum_follow = remainder + offset;
3728 remainder = 0;
3729 }
3730 }
3731
3732 while ((op1_follow != op1) && (remainder != 0))
3733 {
3734 --op1_follow;
3735 --sum_follow;
3736 remainder += (*op1_follow - offset);
3737 if (remainder < 0)
3738 {
3739 *sum_follow = (remainder + base) + offset;
3740 remainder = -1;
3741 }
3742 else
3743 {
3744 *sum_follow = remainder + offset;
3745 remainder = 0;
3746 }
3747 }
3748
3749 while (op1_follow != op1)
3750 {
3751 --op1_follow;
3752 --sum_follow;
3753 *sum_follow = *op1_follow;
3754 }
3755
3756 assert(sum_follow == &(result[0]));
3757 assert(remainder == 0);
3758 }
3759
3760 /* This assumes that op1_len >= op2_len and that the space in scratch
3761 * is >= (9 * op1_len). The result will have length op1_len +
3762 * op2_len. */
3763 static void multiply_string_magnitudes(char *result, char *scratch, char *op1,
3764 char *op2, unsigned long op1_len,
3765 unsigned long op2_len, int base,
3766 int offset)
3767 {
3768 assert((base >= 2) && (base - 1 <= CHAR_MAX - offset));
3769 assert(base <= INT_MAX / 2);
3770 assert(base - 1 <= (INT_MAX - 2 * (base - 1))/(base - 1));
3771 if (INT_MAX + INT_MIN > 0)
3772 assert(base <= NEG_INT_MIN);
3773 else if (INT_MAX + INT_MIN < 0)
3774 assert(-base >= INT_MIN);
3775
3776 if (op2_len == 0)
3777 {
3778 strncpy(result, op1, op1_len);
3779 return;
3780 }
3781
3782 if (op1_len <= CUTOFF)
3783 {
3784 char *result_start = &(result[op1_len + (op2_len - 1)]);
3785 char *result_follow = result_start;
3786 char *op1_follow = &(op1[op1_len - 1]);
3787 char *op2_follow = &(op2[op2_len - 1]);
3788 int carry = 0;
3789 int this_digit = (*op2_follow - offset);
3790 if (this_digit == 0)
3791 {
3792 *result_follow = offset;
3793 }
3794 else
3795 {
3796 while (TRUE)
3797 {
3798 carry += (*op1_follow - offset) * this_digit;
3799 *result_follow = ((char)(carry % base)) + offset;
3800 carry /= base;
3801 assert(carry <= base - 2);
3802 if (op1_follow == op1)
3803 break;
3804 assert(result_follow > result);
3805 --op1_follow;
3806 --result_follow;
3807 }
3808 if (carry != 0)
3809 {
3810 assert(result_follow > result);
3811 --result_follow;
3812 *result_follow = carry + offset;
3813 }
3814 }
3815 while (result_follow > result)
3816 {
3817 --result_follow;
3818 *result_follow = offset;
3819 }
3820
3821 while (op2_follow > op2)
3822 {
3823 --op2_follow;
3824 assert(result_start > result);
3825 --result_start;
3826 result_follow = result_start;
3827 op1_follow = &(op1[op1_len - 1]);
3828 carry = 0;
3829 this_digit = (*op2_follow - offset);
3830 if (this_digit != 0)
3831 {
3832 while (TRUE)
3833 {
3834 carry += (*result_follow - offset);
3835 carry += (*op1_follow - offset) * this_digit;
3836 *result_follow = ((char)(carry % base)) + offset;
3837 carry /= base;
3838 assert(carry <= base - 1);
3839 if (op1_follow == op1)
3840 break;
3841 assert(result_follow > result);
3842 --op1_follow;
3843 --result_follow;
3844 }
3845 if (carry != 0)
3846 {
3847 assert(result_follow > result);
3848 --result_follow;
3849 *result_follow = carry + offset;
3850 }
3851 }
3852 }
3853 }
3854 else
3855 {
3856 unsigned long piece_length =
3857 (op1_len / 2) + (((op1_len % 2) == 0) ? 0 : 1);
3858 if (op2_len <= piece_length)
3859 {
3860 // DLH comments
3861 // piece_length = roundup(op1_len/2)
3862 // Let's figure this out.
3863 // we want to
3864 // 1) partition op1 into (v1 x BASE^n + v2)
3865 // 2) multiply each part by op2.
3866 // 3) add them in the end.
3867 // example is base 10.
3868 // 22222 222222
3869 // x 5
3870 // ------------
3871 // 111110 000000
3872 // + 1 111110
3873 // -------------
3874 // 111111 111110
3875 //
3876 // build a result with the right number of zeros.
3877 // assume there are op1_len + op2_len digits available
3878 // with a \0 already at the end?
3879 // I've tested this against bc on Factorial and FactorialSquared
3880 // from 1 to 300.
3881 memset(result, offset, op1_len + op2_len);
3882 multiply_string_magnitudes(&(result[0]),
3883 scratch,
3884 op1, op2,
3885 op1_len - piece_length,
3886 op2_len, base, offset);
3887 multiply_string_magnitudes(scratch,
3888 &(scratch[op2_len + piece_length]),
3889 &(op1[op1_len - piece_length]),
3890 op2,
3891 piece_length, op2_len,
3892 base, offset);
3893 add_to_string_magnitude(result, scratch,
3894 op1_len + op2_len,
3895 op2_len + piece_length, base,
3896 offset);
3897 return;
3898 }
3899 multiply_string_magnitudes(result, scratch, op1, op2,
3900 op1_len - piece_length,
3901 op2_len - piece_length, base, offset);
3902 multiply_string_magnitudes(&(result[op1_len + op2_len -
3903 (2 * piece_length)]), scratch,
3904 &(op1[op1_len - piece_length]),
3905 &(op2[op2_len - piece_length]),
3906 piece_length, piece_length, base, offset);
3907 add_string_magnitudes(&(scratch[2 * piece_length + 2]),
3908 &(op1[op1_len - piece_length]), op1,
3909 piece_length, op1_len - piece_length, base,
3910 offset);
3911 add_string_magnitudes(&(scratch[3 * piece_length + 3]),
3912 &(op2[op2_len - piece_length]), op2,
3913 piece_length, op2_len - piece_length, base,
3914 offset);
3915 multiply_string_magnitudes(scratch, &(scratch[4 * piece_length + 4]),
3916 &(scratch[2 * piece_length + 2]),
3917 &(scratch[3 * piece_length + 3]),
3918 piece_length + 1, piece_length + 1, base,
3919 offset);
3920 assert(scratch[0] == offset);
3921 subtract_string_magnitudes(&(scratch[2 * piece_length + 2]),
3922 &(scratch[1]), result, 2 * piece_length + 1,
3923 op1_len + op2_len - (2 * piece_length),
3924 base, offset);
3925 subtract_string_magnitudes(scratch, &(scratch[2 * piece_length + 2]),
3926 &(result[op1_len + op2_len -
3927 (2 * piece_length)]),
3928 2 * piece_length + 1, 2 * piece_length,
3929 base, offset);
3930 add_to_string_magnitude(result, scratch,
3931 op1_len + op2_len - piece_length,
3932 2 * piece_length + 1, base, offset);
3933 }
3934 }
3935
3936 /* This assumes that op1_len >= op2_len. div_result will have length
3937 * op1_len - op2_len + 1, and mod_result will have length op2_len. */
3938 static void divide_string_magnitudes(char *div_result, char *mod_result,
3939 char *op1, char *op2,
3940 unsigned long op1_len,
3941 unsigned long op2_len, int offset)
3942 {
3943 static char *factors[9] =
3944 { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL };
3945 static unsigned long factor_length;
3946 static char *remainder = NULL;
3947 static char *alt_remainder = NULL;
3948 static unsigned long remainder_length;
3949
3950 if ((factors[0] == NULL) || (factor_length < op1_len + 1))
3951 {
3952 if (factors[0] != NULL)
3953 {
3954 for (int index = 0; index < 9; ++index)
3955 delete[] factors[index];
3956 }
3957 factor_length = op1_len + 1;
3958 for (int index = 0; index < 9; ++index)
3959 factors[index] = new char[factor_length];
3960 }
3961
3962 if ((remainder == NULL) || (remainder_length < op1_len))
3963 {
3964 if (remainder != NULL)
3965 {
3966 delete[] remainder;
3967 delete[] alt_remainder;
3968 }
3969 remainder_length = op1_len;
3970 remainder = new char[remainder_length];
3971 alt_remainder = new char[remainder_length];
3972 }
3973
3974 for (int index = 0; index < 9; ++index)
3975 {
3976 if (op1_len > op2_len)
3977 memset(&(factors[index][op2_len + 1]), offset, op1_len - op2_len);
3978 int carry = 0;
3979 char *follow_factor = &(factors[index][op2_len]);
3980 char *follow_op2 = &(op2[op2_len - 1]);
3981 while (TRUE)
3982 {
3983 carry += (*follow_op2 - offset) * (index + 1);
3984 *follow_factor = ((char)(carry % 10)) + offset;
3985 carry /= 10;
3986 assert(carry <= 8);
3987 --follow_factor;
3988 if (follow_op2 == op2)
3989 break;
3990 assert(follow_factor > factors[index]);
3991 --follow_op2;
3992 }
3993 assert(follow_factor == factors[index]);
3994 *follow_factor = carry + offset;
3995 }
3996
3997 memcpy(remainder, op1, op1_len);
3998
3999 char *follow_div = div_result;
4000 char *div_end = &(div_result[op1_len - op2_len]);
4001 unsigned long this_factor_length = op1_len + 1;
4002 while (TRUE)
4003 {
4004 int this_digit;
4005 if (string_magnitude_is_less(remainder, factors[4], op1_len,
4006 this_factor_length, offset))
4007 {
4008 if (string_magnitude_is_less(remainder, factors[2], op1_len,
4009 this_factor_length, offset))
4010 {
4011 if (string_magnitude_is_less(remainder, factors[1], op1_len,
4012 this_factor_length, offset))
4013 {
4014 if (string_magnitude_is_less(remainder, factors[0],
4015 op1_len, this_factor_length,
4016 offset))
4017 {
4018 this_digit = 0;
4019 }
4020 else
4021 {
4022 this_digit = 1;
4023 }
4024 }
4025 else
4026 {
4027 this_digit = 2;
4028 }
4029 }
4030 else
4031 {
4032 if (string_magnitude_is_less(remainder, factors[3], op1_len,
4033 this_factor_length, offset))
4034 {
4035 this_digit = 3;
4036 }
4037 else
4038 {
4039 this_digit = 4;
4040 }
4041 }
4042 }
4043 else
4044 {
4045 if (string_magnitude_is_less(remainder, factors[7], op1_len,
4046 this_factor_length, offset))
4047 {
4048 if (string_magnitude_is_less(remainder, factors[6], op1_len,
4049 this_factor_length, offset))
4050 {
4051 if (string_magnitude_is_less(remainder, factors[5],
4052 op1_len, this_factor_length,
4053 offset))
4054 {
4055 this_digit = 5;
4056 }
4057 else
4058 {
4059 this_digit = 6;
4060 }
4061 }
4062 else
4063 {
4064 this_digit = 7;
4065 }
4066 }
4067 else
4068 {
4069 if (string_magnitude_is_less(remainder, factors[8], op1_len,
4070 this_factor_length, offset))
4071 {
4072 this_digit = 8;
4073 }
4074 else
4075 {
4076 this_digit = 9;
4077 }
4078 }
4079 }
4080
4081 *follow_div = this_digit + offset;
4082 if (this_digit > 0)
4083 {
4084 unsigned fact_len = this_factor_length;
4085 char *this_factor = factors[this_digit - 1];
4086 while ((fact_len > 1) && (*this_factor == offset))
4087 {
4088 --fact_len;
4089 ++this_factor;
4090 }
4091 subtract_string_magnitudes(alt_remainder, remainder, this_factor,
4092 op1_len, fact_len, 10, offset);
4093 char *temp = alt_remainder;
4094 alt_remainder = remainder;
4095 remainder = temp;
4096 }
4097
4098 if (follow_div == div_end)
4099 break;
4100 ++follow_div;
4101 assert(this_factor_length > op2_len + 1);
4102 --this_factor_length;
4103 }
4104 assert(this_factor_length == op2_len + 1);
4105 for (unsigned long ul_index = 0; ul_index < op1_len - op2_len; ++ul_index)
4106 assert(remainder[ul_index] == offset);
4107
4108 memcpy(mod_result, &(remainder[op1_len - op2_len]), op2_len);
4109 }
4110
4111 static void justify_int_string(char *string, unsigned long size, int offset)
4112 {
4113 char *zero_follow = string;
4114 while ((zero_follow + 1 < &(string[size])) &&
4115 (*zero_follow == offset))
4116 {
4117 ++zero_follow;
4118 }
4119 unsigned long zero_count = zero_follow - string;
4120 if (zero_count > 0)
4121 memmove(string, zero_follow, size - zero_count);
4122 string[size - zero_count] = 0;
4123 }
4124
4125 /* This assumes that the space in scratch is >= (9 * <result size>). The
4126 * result will have length old_size * ceil(log_new_base(old_base)). */
4127 static void base_convert(char *new_string, char *scratch, char *old_string,
4128 unsigned long old_size, int old_base, int new_base,
4129 int old_offset, int new_offset)
4130 {
4131 assert((new_base >= 2) && (new_base - 1 <= CHAR_MAX - new_offset));
4132 assert((old_base >= 2) && (old_base - 1 <= CHAR_MAX - old_offset));
4133 assert(old_base <= LONG_MAX / old_base);
4134
4135 if (new_base == old_base)
4136 {
4137 strcpy(new_string, old_string);
4138 return;
4139 }
4140
4141 if (old_size == 0)
4142 return;
4143
4144 /* set blow_up_factor = ceil(log_new_base(old_base)) */
4145 int blow_up = blow_up_factor(old_base, new_base);
4146
4147 if (old_size <= 2)
4148 {
4149 long old_digit = *old_string - old_offset;
4150 assert(old_digit < old_base);
4151 if (old_size == 2)
4152 {
4153 assert(old_string[1] - old_offset < old_base);
4154 old_digit *= old_base;
4155 old_digit += (old_string[1] - old_offset);
4156 }
4157 char *follow_new = &(new_string[old_size * blow_up - 1]);
4158 while (TRUE)
4159 {
4160 *follow_new = ((char)(old_digit % new_base)) + new_offset;
4161 old_digit /= new_base;
4162 if (follow_new == new_string)
4163 break;
4164 --follow_new;
4165 }
4166 assert(old_digit == 0);
4167 return;
4168 }
4169
4170 unsigned long right_size = old_size / 2;
4171 unsigned long left_size = old_size - right_size;
4172 char *s1 = &(scratch[(right_size + 1) * blow_up]);
4173 char *s2 = &(s1[right_size + 1]);
4174 char *s3 = &(s2[left_size * blow_up]);
4175
4176 base_convert(s2, s3, old_string, left_size, old_base, new_base,
4177 old_offset, new_offset);
4178
4179 /* set s1 = "1000...00" */
4180 s1[0] = 1 + old_offset;
4181 char *follow_s1 = s1;
4182 char *end_s1 = &(s1[right_size]);
4183 while (follow_s1 != end_s1)
4184 {
4185 ++follow_s1;
4186 *follow_s1 = old_offset;
4187 }
4188
4189 base_convert(scratch, s3, s1, right_size + 1, old_base, new_base,
4190 old_offset, new_offset);
4191 for (int index = 0; index < blow_up; ++index)
4192 assert(scratch[index] == new_offset);
4193 multiply_string_magnitudes(new_string, s3, s2, &(scratch[blow_up]),
4194 left_size * blow_up, right_size * blow_up,
4195 new_base, new_offset);
4196 base_convert(scratch, &(scratch[right_size * blow_up]),
4197 &(old_string[left_size]), right_size, old_base, new_base,
4198 old_offset, new_offset);
4199 add_to_string_magnitude(new_string, scratch, old_size * blow_up,
4200 right_size * blow_up, new_base, new_offset);
4201 }
4202
4203 /* return ceil(log_new_base(old_base)) */
4204 static int blow_up_factor(int old_base, int new_base)
4205 {
4206 int result = 0;
4207 int remainder = old_base - 1;
4208 while (remainder > 0)
4209 {
4210 remainder /= new_base;
4211 ++result;
4212 }
4213 return result;
4214 }
4215
4216 static i_rational read_digits_with_decimal_point(const char **location,
4217 int base)
4218 {
4219 i_integer pre_decimal_point(*location, base);
4220
4221 const char *follow_string = *location;
4222
4223 while (isspace(*follow_string))
4224 ++follow_string;
4225
4226 if (*follow_string == '-')
4227 ++follow_string;
4228
4229 while (isspace(*follow_string))
4230 ++follow_string;
4231
4232 while (*follow_string != 0)
4233 {
4234 int this_digit = *follow_string;
4235 if ((this_digit >= '0') && (this_digit <= '9'))
4236 this_digit -= '0';
4237 else if ((this_digit >= 'a') && (this_digit <= 'z'))
4238 this_digit -= ('a' - 10);
4239 else if ((this_digit >= 'A') && (this_digit <= 'Z'))
4240 this_digit -= ('A' - 10);
4241 else
4242 break;
4243
4244 if (this_digit >= base)
4245 break;
4246
4247 ++follow_string;
4248 }
4249
4250 if (*follow_string != '.')
4251 {
4252 *location = follow_string;
4253 return pre_decimal_point;
4254 }
4255
4256 const char *decimal_place = follow_string;
4257
4258 ++follow_string;
4259
4260 while (*follow_string != 0)
4261 {
4262 int this_digit = *follow_string;
4263 if ((this_digit >= '0') && (this_digit <= '9'))
4264 this_digit -= '0';
4265 else if ((this_digit >= 'a') && (this_digit <= 'z'))
4266 this_digit -= ('a' - 10);
4267 else if ((this_digit >= 'A') && (this_digit <= 'Z'))
4268 this_digit -= ('A' - 10);
4269 else
4270 break;
4271
4272 if (this_digit >= base)
4273 break;
4274
4275 ++follow_string;
4276 }
4277
4278 *location = follow_string;
4279
4280 if (follow_string == decimal_place + 1)
4281 return pre_decimal_point;
4282
4283 i_integer post_decimal_point(decimal_place + 1, base);
4284
4285 i_integer denominator = 1;
4286 while (follow_string > decimal_place + 1)
4287 {
4288 denominator *= base;
4289 --follow_string;
4290 }
4291
4292 return i_rational(pre_decimal_point) +
4293 i_rational(post_decimal_point, denominator);
4294 }
4295
4296 /*----------------------------------------------------------------------*
4297 End Private Function Implementations
4298 *----------------------------------------------------------------------*/