-/*
- Copyright (C) 1989-94 Massachusetts Institute of Technology
- Portions copyright (C) 2004-2008 Slava Pestov
-
- This material was developed by the Scheme project at the Massachusetts
- Institute of Technology, Department of Electrical Engineering and
- Computer Science. Permission to copy and modify this software, to
- redistribute either the original software or a modified version, and
- to use this software for any purpose is granted, subject to the
- following restrictions and understandings.
-
- 1. Any copy made of this software must include this copyright notice
- in full.
-
- 2. Users of this software agree to make their best efforts (a) to
- return to the MIT Scheme project any improvements or extensions that
- they make, so that these may be included in future releases; and (b)
- to inform MIT of noteworthy uses of this software.
-
- 3. All materials developed as a consequence of the use of this
- software shall duly acknowledge such use, in accordance with the usual
- standards of acknowledging credit in academic research.
-
- 4. MIT has made no warrantee or representation that the operation of
- this software will be error-free, and MIT is under no obligation to
- provide any services, by way of maintenance, update, or otherwise.
-
- 5. In conjunction with products arising from the use of this material,
- there shall be no use of the name of the Massachusetts Institute of
- Technology nor of any adaptation thereof in any advertising,
- promotional, or sales literature without prior written consent from
- MIT in each case. */
-
-/* Changes for Scheme 48:
- * - Converted to ANSI.
- * - Added bitwise operations.
- * - Added s48 to the beginning of all externally visible names.
- * - Cached the bignum representations of -1, 0, and 1.
- */
-
-/* Changes for Factor:
- * - Adapt bignumint.h for Factor memory manager
- * - Add more bignum <-> C type conversions
- * - Remove unused functions
- * - Add local variable GC root recording
- * - Remove s48 prefix from function names
- * - Various fixes for Win64
- * - Port to C++
- * - Added bignum_gcd implementation
- */
+// Copyright (C) 1989-94 Massachusetts Institute of Technology
+// Portions copyright (C) 2004-2008 Slava Pestov
+
+// This material was developed by the Scheme project at the Massachusetts
+// Institute of Technology, Department of Electrical Engineering and
+// Computer Science. Permission to copy and modify this software, to
+// redistribute either the original software or a modified version, and
+// to use this software for any purpose is granted, subject to the
+// following restrictions and understandings.
+
+// 1. Any copy made of this software must include this copyright notice
+// in full.
+
+// 2. Users of this software agree to make their best efforts (a) to
+// return to the MIT Scheme project any improvements or extensions that
+// they make, so that these may be included in future releases; and (b)
+// to inform MIT of noteworthy uses of this software.
+
+// 3. All materials developed as a consequence of the use of this
+// software shall duly acknowledge such use, in accordance with the usual
+// standards of acknowledging credit in academic research.
+
+// 4. MIT has made no warrantee or representation that the operation of
+// this software will be error-free, and MIT is under no obligation to
+// provide any services, by way of maintenance, update, or otherwise.
+
+// 5. In conjunction with products arising from the use of this material,
+// there shall be no use of the name of the Massachusetts Institute of
+// Technology nor of any adaptation thereof in any advertising,
+// promotional, or sales literature without prior written consent from
+// MIT in each case.
+
+// Changes for Scheme 48:
+// * - Converted to ANSI.
+// * - Added bitwise operations.
+// * - Added s48 to the beginning of all externally visible names.
+// * - Cached the bignum representations of -1, 0, and 1.
+
+// Changes for Factor:
+// * - Adapt bignumint.h for Factor memory manager
+// * - Add more bignum <-> C type conversions
+// * - Remove unused functions
+// * - Add local variable GC root recording
+// * - Remove s48 prefix from function names
+// * - Various fixes for Win64
+// * - Port to C++
+// * - Added bignum_gcd implementation
#include "master.hpp"
namespace factor {
-/* Exports */
+// Exports
int factor_vm::bignum_equal_p(bignum* x, bignum* y) {
return ((BIGNUM_ZERO_P(x))
}
enum bignum_comparison factor_vm::bignum_compare(bignum* x, bignum* y) {
- return ((BIGNUM_ZERO_P(x)) ? ((BIGNUM_ZERO_P(y)) ? bignum_comparison_equal
+ return ((BIGNUM_ZERO_P(x)) ? ((BIGNUM_ZERO_P(y)) ? BIGNUM_COMPARISON_EQUAL
: (BIGNUM_NEGATIVE_P(y))
- ? bignum_comparison_greater
- : bignum_comparison_less)
+ ? BIGNUM_COMPARISON_GREATER
+ : BIGNUM_COMPARISON_LESS)
: (BIGNUM_ZERO_P(y))
- ? ((BIGNUM_NEGATIVE_P(x)) ? bignum_comparison_less
- : bignum_comparison_greater)
+ ? ((BIGNUM_NEGATIVE_P(x)) ? BIGNUM_COMPARISON_LESS
+ : BIGNUM_COMPARISON_GREATER)
: (BIGNUM_NEGATIVE_P(x))
? ((BIGNUM_NEGATIVE_P(y)) ? (bignum_compare_unsigned(y, x))
- : (bignum_comparison_less))
- : ((BIGNUM_NEGATIVE_P(y)) ? (bignum_comparison_greater)
+ : (BIGNUM_COMPARISON_LESS))
+ : ((BIGNUM_NEGATIVE_P(y)) ? (BIGNUM_COMPARISON_GREATER)
: (bignum_compare_unsigned(x, y))));
}
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::bignum_add(bignum* x, bignum* y) {
return (
(BIGNUM_ZERO_P(x)) ? (y) : (BIGNUM_ZERO_P(y))
: (bignum_add_unsigned(x, y, 0)))));
}
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::bignum_subtract(bignum* x, bignum* y) {
return ((BIGNUM_ZERO_P(x))
? ((BIGNUM_ZERO_P(y)) ? (y) : (bignum_new_sign(
: (bignum_subtract_unsigned(x, y))))));
}
-/* Allocates memory */
+#ifdef _WIN64
+bignum *factor_vm::bignum_square(bignum* x_)
+{
+ return bignum_multiply(x_, x_);
+}
+#else
+// Allocates memory
+bignum *factor_vm::bignum_square(bignum* x_)
+{
+ data_root<bignum> x(x_, this);
+
+ bignum_length_type length = (BIGNUM_LENGTH (x));
+ bignum * z = (allot_bignum_zeroed ((length + length), 0));
+
+ bignum_digit_type * scan_z = BIGNUM_START_PTR (z);
+ bignum_digit_type * scan_x = BIGNUM_START_PTR (x);
+ bignum_digit_type * end_x = scan_x + length;
+
+ for (int i = 0; i < length; ++i) {
+ bignum_twodigit_type carry;
+ bignum_twodigit_type f = BIGNUM_REF (x, i);
+ bignum_digit_type *pz = scan_z + (i << 1);
+ bignum_digit_type *px = scan_x + i + 1;
+
+ carry = *pz + f * f;
+ *pz++ = carry & BIGNUM_DIGIT_MASK;
+ carry >>= BIGNUM_DIGIT_LENGTH;
+ BIGNUM_ASSERT (carry <= BIGNUM_DIGIT_MASK);
+
+ f <<= 1;
+ while (px < end_x)
+ {
+ carry += *pz + *px++ * f;
+ *pz++ = carry & BIGNUM_DIGIT_MASK;
+ carry >>= BIGNUM_DIGIT_LENGTH;
+ BIGNUM_ASSERT (carry <= (BIGNUM_DIGIT_MASK << 1));
+ }
+ if (carry) {
+ carry += *pz;
+ *pz++ = carry & BIGNUM_DIGIT_MASK;
+ carry >>= BIGNUM_DIGIT_LENGTH;
+ }
+ if (carry)
+ *pz += carry & BIGNUM_DIGIT_MASK;
+ BIGNUM_ASSERT ((carry >> BIGNUM_DIGIT_LENGTH) == 0);
+ }
+ return (bignum_trim (z));
+}
+#endif
+
+// Allocates memory
bignum* factor_vm::bignum_multiply(bignum* x, bignum* y) {
+
+#ifndef _WIN64
+ if (x == y) {
+ return bignum_square(x);
+ }
+#endif
+
bignum_length_type x_length = (BIGNUM_LENGTH(x));
bignum_length_type y_length = (BIGNUM_LENGTH(y));
int negative_p = ((BIGNUM_NEGATIVE_P(x)) ? (!(BIGNUM_NEGATIVE_P(y)))
return (bignum_multiply_unsigned(x, y, negative_p));
}
-/* Allocates memory */
+// Allocates memory
void factor_vm::bignum_divide(bignum* numerator, bignum* denominator,
bignum** quotient, bignum** remainder) {
if (BIGNUM_ZERO_P(denominator)) {
int q_negative_p =
((BIGNUM_NEGATIVE_P(denominator)) ? (!r_negative_p) : r_negative_p);
switch (bignum_compare_unsigned(numerator, denominator)) {
- case bignum_comparison_equal: {
+ case BIGNUM_COMPARISON_EQUAL: {
(*quotient) = (BIGNUM_ONE(q_negative_p));
(*remainder) = (BIGNUM_ZERO());
break;
}
- case bignum_comparison_less: {
+ case BIGNUM_COMPARISON_LESS: {
(*quotient) = (BIGNUM_ZERO());
(*remainder) = numerator;
break;
}
- case bignum_comparison_greater: {
+ case BIGNUM_COMPARISON_GREATER: {
if ((BIGNUM_LENGTH(denominator)) == 1) {
bignum_digit_type digit = (BIGNUM_REF(denominator, 0));
if (digit == 1) {
}
}
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::bignum_quotient(bignum* numerator, bignum* denominator) {
if (BIGNUM_ZERO_P(denominator)) {
divide_by_zero_error();
((BIGNUM_NEGATIVE_P(denominator)) ? (!(BIGNUM_NEGATIVE_P(numerator)))
: (BIGNUM_NEGATIVE_P(numerator)));
switch (bignum_compare_unsigned(numerator, denominator)) {
- case bignum_comparison_equal:
+ case BIGNUM_COMPARISON_EQUAL:
return (BIGNUM_ONE(q_negative_p));
- case bignum_comparison_less:
+ case BIGNUM_COMPARISON_LESS:
return (BIGNUM_ZERO());
- case bignum_comparison_greater:
- default: /* to appease gcc -Wall */
+ case BIGNUM_COMPARISON_GREATER:
+ default: // to appease gcc -Wall
{
bignum* quotient;
if ((BIGNUM_LENGTH(denominator)) == 1) {
}
}
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::bignum_remainder(bignum* numerator, bignum* denominator) {
if (BIGNUM_ZERO_P(denominator)) {
divide_by_zero_error();
if (BIGNUM_ZERO_P(numerator))
return numerator;
switch (bignum_compare_unsigned(numerator, denominator)) {
- case bignum_comparison_equal:
+ case BIGNUM_COMPARISON_EQUAL:
return (BIGNUM_ZERO());
- case bignum_comparison_less:
+ case BIGNUM_COMPARISON_LESS:
return numerator;
- case bignum_comparison_greater:
- default: /* to appease gcc -Wall */
+ case BIGNUM_COMPARISON_GREATER:
+ default: // to appease gcc -Wall
{
bignum* remainder;
if ((BIGNUM_LENGTH(denominator)) == 1) {
}
}
-/* cell_to_bignum, fixnum_to_bignum, long_long_to_bignum, ulong_long_to_bignum
- */
-/* Allocates memory */
-#define FOO_TO_BIGNUM(name, type, stype, utype) \
+// cell_to_bignum, fixnum_to_bignum, long_long_to_bignum, ulong_long_to_bignum
+
+// Allocates memory
+#define FOO_TO_BIGNUM_SIGNED(name, type, utype) \
bignum* factor_vm::name##_to_bignum(type n) { \
int negative_p; \
- bignum_digit_type result_digits[BIGNUM_DIGITS_FOR(type)]; \
- bignum_digit_type* end_digits = result_digits; \
/* Special cases win when these small constants are cached. */ \
if (n == 0) \
return (BIGNUM_ZERO()); \
if (n == 1) \
return (BIGNUM_ONE(0)); \
- if (n < (type) 0 && n == (type) - 1) \
+ if (n < (type) 0 && n == (type) -1) \
return (BIGNUM_ONE(1)); \
{ \
utype accumulator = \
- ((negative_p = (n < (type) 0)) ? ((type)(-(stype) n)) : n); \
- do { \
- (*end_digits++) = (accumulator & BIGNUM_DIGIT_MASK); \
- accumulator >>= BIGNUM_DIGIT_LENGTH; \
- } while (accumulator != 0); \
+ ((negative_p = n < (type) 0) ? -n : n); \
+ if (accumulator < BIGNUM_RADIX) \
+ { \
+ bignum* result = allot_bignum(1, negative_p); \
+ bignum_digit_type* scan = (BIGNUM_START_PTR(result)); \
+ *scan = (accumulator & BIGNUM_DIGIT_MASK); \
+ return (result); \
+ } else { \
+ bignum_digit_type result_digits[BIGNUM_DIGITS_FOR(type)]; \
+ bignum_digit_type* end_digits = result_digits; \
+ do { \
+ (*end_digits++) = (accumulator & BIGNUM_DIGIT_MASK); \
+ accumulator >>= BIGNUM_DIGIT_LENGTH; \
+ } while (accumulator != 0); \
+ bignum* result = \
+ (allot_bignum((end_digits - result_digits), negative_p)); \
+ bignum_digit_type* scan_digits = result_digits; \
+ bignum_digit_type* scan_result = (BIGNUM_START_PTR(result)); \
+ while (scan_digits < end_digits) \
+ (*scan_result++) = (*scan_digits++); \
+ return (result); \
+ } \
} \
+ }
+
+// Allocates memory
+#define FOO_TO_BIGNUM_UNSIGNED(name, type, utype) \
+ bignum* factor_vm::name##_to_bignum(type n) { \
+ /* Special cases win when these small constants are cached. */ \
+ if (n == 0) \
+ return (BIGNUM_ZERO()); \
+ if (n == 1) \
+ return (BIGNUM_ONE(0)); \
{ \
- bignum* result = \
- (allot_bignum((end_digits - result_digits), negative_p)); \
- bignum_digit_type* scan_digits = result_digits; \
- bignum_digit_type* scan_result = (BIGNUM_START_PTR(result)); \
- while (scan_digits < end_digits) \
- (*scan_result++) = (*scan_digits++); \
- return (result); \
+ utype accumulator = n; \
+ if (accumulator < BIGNUM_RADIX) \
+ { \
+ bignum* result = allot_bignum(1, false); \
+ bignum_digit_type* scan = (BIGNUM_START_PTR(result)); \
+ *scan = (accumulator & BIGNUM_DIGIT_MASK); \
+ return (result); \
+ } else { \
+ bignum_digit_type result_digits[BIGNUM_DIGITS_FOR(type)]; \
+ bignum_digit_type* end_digits = result_digits; \
+ do { \
+ (*end_digits++) = (accumulator & BIGNUM_DIGIT_MASK); \
+ accumulator >>= BIGNUM_DIGIT_LENGTH; \
+ } while (accumulator != 0); \
+ bignum* result = \
+ (allot_bignum((end_digits - result_digits), false)); \
+ bignum_digit_type* scan_digits = result_digits; \
+ bignum_digit_type* scan_result = (BIGNUM_START_PTR(result)); \
+ while (scan_digits < end_digits) \
+ (*scan_result++) = (*scan_digits++); \
+ return (result); \
+ } \
} \
}
-FOO_TO_BIGNUM(cell, cell, fixnum, cell)
-FOO_TO_BIGNUM(fixnum, fixnum, fixnum, cell)
-FOO_TO_BIGNUM(long_long, int64_t, int64_t, uint64_t)
-FOO_TO_BIGNUM(ulong_long, uint64_t, int64_t, uint64_t)
+FOO_TO_BIGNUM_SIGNED(fixnum, fixnum, cell)
+FOO_TO_BIGNUM_UNSIGNED(cell, cell, cell)
+FOO_TO_BIGNUM_SIGNED(long_long, int64_t, uint64_t)
+FOO_TO_BIGNUM_UNSIGNED(ulong_long, uint64_t, uint64_t)
-/* cannot allocate memory */
-/* bignum_to_cell, fixnum_to_cell, long_long_to_cell, ulong_long_to_cell */
+// cannot allocate memory
+// bignum_to_cell, fixnum_to_cell, long_long_to_cell, ulong_long_to_cell
#define BIGNUM_TO_FOO(name, type, stype, utype) \
- type factor_vm::bignum_to_##name(bignum * bignum) { \
- if (BIGNUM_ZERO_P(bignum)) \
+ type bignum_to_##name(bignum* bn) { \
+ if (BIGNUM_ZERO_P(bn)) \
return (0); \
{ \
utype accumulator = 0; \
- bignum_digit_type* start = (BIGNUM_START_PTR(bignum)); \
- bignum_digit_type* scan = (start + (BIGNUM_LENGTH(bignum))); \
+ bignum_digit_type* start = (BIGNUM_START_PTR(bn)); \
+ bignum_digit_type* scan = (start + (BIGNUM_LENGTH(bn))); \
while (start < scan) \
accumulator = ((accumulator << BIGNUM_DIGIT_LENGTH) + (*--scan)); \
- return ((BIGNUM_NEGATIVE_P(bignum)) ? ((type)(-(stype) accumulator)) \
- : accumulator); \
+ return ((BIGNUM_NEGATIVE_P(bn)) ? ((type)(-(stype) accumulator)) \
+ : accumulator); \
} \
}
BIGNUM_TO_FOO(long_long, int64_t, int64_t, uint64_t)
BIGNUM_TO_FOO(ulong_long, uint64_t, int64_t, uint64_t)
+bool bignum_fits_fixnum_p(bignum* bn) {
+ fixnum len = BIGNUM_LENGTH(bn);
+ if (len == 0)
+ return true;
+ if (len > 1)
+ return false;
+ bignum_digit_type dig = BIGNUM_START_PTR(bn)[0];
+ return (BIGNUM_NEGATIVE_P(bn) && dig <= -fixnum_min) ||
+ (!BIGNUM_NEGATIVE_P(bn) && dig <= fixnum_max);
+}
+
+cell bignum_maybe_to_fixnum(bignum* bn) {
+ if (bignum_fits_fixnum_p(bn))
+ return tag_fixnum(bignum_to_fixnum(bn));
+ return tag<bignum>(bn);
+}
+
+// cannot allocate memory
+fixnum factor_vm::bignum_to_fixnum_strict(bignum* bn) {
+
+ if (!bignum_fits_fixnum_p(bn)) {
+ general_error(ERROR_OUT_OF_FIXNUM_RANGE, tag<bignum>(bn), false_object);
+ }
+ fixnum fix = bignum_to_fixnum(bn);
+ FACTOR_ASSERT(fix <= fixnum_max && fix >= fixnum_min);
+ return fix;
+}
+
#define DTB_WRITE_DIGIT(factor) \
{ \
significand *= (factor); \
digit = ((bignum_digit_type) significand); \
(*--scan) = digit; \
- significand -= ((double) digit); \
+ significand -= ((double)digit); \
}
#define inf std::numeric_limits<double>::infinity()
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::double_to_bignum(double x) {
if (x == inf || x == -inf || x != x)
return (BIGNUM_ZERO());
bignum_digit_type digit;
int odd_bits = (exponent % BIGNUM_DIGIT_LENGTH);
if (odd_bits > 0)
- DTB_WRITE_DIGIT((fixnum) 1 << odd_bits);
+ DTB_WRITE_DIGIT((fixnum)1 << odd_bits);
while (start < scan) {
if (significand == 0) {
while (start < scan)
#undef DTB_WRITE_DIGIT
-/* Comparisons */
+// Comparisons
int factor_vm::bignum_equal_p_unsigned(bignum* x, bignum* y) {
bignum_length_type length = (BIGNUM_LENGTH(x));
bignum_length_type x_length = (BIGNUM_LENGTH(x));
bignum_length_type y_length = (BIGNUM_LENGTH(y));
if (x_length < y_length)
- return (bignum_comparison_less);
+ return BIGNUM_COMPARISON_LESS;
if (x_length > y_length)
- return (bignum_comparison_greater);
+ return BIGNUM_COMPARISON_GREATER;
{
bignum_digit_type* start_x = (BIGNUM_START_PTR(x));
bignum_digit_type* scan_x = (start_x + x_length);
bignum_digit_type digit_x = (*--scan_x);
bignum_digit_type digit_y = (*--scan_y);
if (digit_x < digit_y)
- return (bignum_comparison_less);
+ return BIGNUM_COMPARISON_LESS;
if (digit_x > digit_y)
- return (bignum_comparison_greater);
+ return BIGNUM_COMPARISON_GREATER;
}
}
- return (bignum_comparison_equal);
+ return BIGNUM_COMPARISON_EQUAL;
}
-/* Addition */
+// Addition
-/* Allocates memory */
-bignum* factor_vm::bignum_add_unsigned(bignum* x, bignum* y, int negative_p) {
- GC_BIGNUM(x);
- GC_BIGNUM(y);
+// Allocates memory
+bignum* factor_vm::bignum_add_unsigned(bignum* x_, bignum* y_, int negative_p) {
+ data_root<bignum> x(x_, this);
+ data_root<bignum> y(y_, this);
if ((BIGNUM_LENGTH(y)) > (BIGNUM_LENGTH(x))) {
- bignum* z = x;
- x = y;
- y = z;
+ swap(x, y);
}
{
bignum_length_type x_length = (BIGNUM_LENGTH(x));
}
}
{
- bignum_digit_type* end_x = ((BIGNUM_START_PTR(x)) + x_length);
+ bignum_digit_type* end_x = BIGNUM_START_PTR(x) + x_length;
if (carry != 0)
while (scan_x < end_x) {
sum = ((*scan_x++) + 1);
}
}
-/* Subtraction */
+// Subtraction
+
+// Allocates memory
+bignum* factor_vm::bignum_subtract_unsigned(bignum* x_, bignum* y_) {
-/* Allocates memory */
-bignum* factor_vm::bignum_subtract_unsigned(bignum* x, bignum* y) {
- GC_BIGNUM(x);
- GC_BIGNUM(y);
+ data_root<bignum> x(x_, this);
+ data_root<bignum> y(y_, this);
int negative_p = 0;
- switch (bignum_compare_unsigned(x, y)) {
- case bignum_comparison_equal:
+ switch (bignum_compare_unsigned(x.untagged(), y.untagged())) {
+ case BIGNUM_COMPARISON_EQUAL:
return (BIGNUM_ZERO());
- case bignum_comparison_less: {
- bignum* z = x;
- x = y;
- y = z;
- }
+ case BIGNUM_COMPARISON_LESS:
+ swap(x, y);
negative_p = 1;
break;
- case bignum_comparison_greater:
+ case BIGNUM_COMPARISON_GREATER:
negative_p = 0;
break;
}
bignum_digit_type difference;
bignum_digit_type borrow = 0;
- bignum_digit_type* scan_x = (BIGNUM_START_PTR(x));
- bignum_digit_type* scan_r = (BIGNUM_START_PTR(r));
+ bignum_digit_type* scan_x = BIGNUM_START_PTR(x);
+ bignum_digit_type* scan_r = BIGNUM_START_PTR(r);
{
- bignum_digit_type* scan_y = (BIGNUM_START_PTR(y));
+ bignum_digit_type* scan_y = BIGNUM_START_PTR(y);
bignum_digit_type* end_y = (scan_y + (BIGNUM_LENGTH(y)));
while (scan_y < end_y) {
difference = (((*scan_x++) - (*scan_y++)) - borrow);
}
}
{
- bignum_digit_type* end_x = ((BIGNUM_START_PTR(x)) + x_length);
+ bignum_digit_type* end_x = BIGNUM_START_PTR(x) + x_length;
if (borrow != 0)
while (scan_x < end_x) {
difference = ((*scan_x++) - borrow);
}
}
-/* Multiplication
- Maximum value for product_low or product_high:
- ((R * R) + (R * (R - 2)) + (R - 1))
- Maximum value for carry: ((R * (R - 1)) + (R - 1))
- where R == BIGNUM_RADIX_ROOT */
+// Multiplication
+// Maximum value for product_low or product_high:
+// ((R * R) + (R * (R - 2)) + (R - 1))
+// Maximum value for carry: ((R * (R - 1)) + (R - 1))
+// where R == BIGNUM_RADIX_ROOT
-/* Allocates memory */
-bignum* factor_vm::bignum_multiply_unsigned(bignum* x, bignum* y,
+// Allocates memory
+bignum* factor_vm::bignum_multiply_unsigned(bignum* x_, bignum* y_,
int negative_p) {
- GC_BIGNUM(x);
- GC_BIGNUM(y);
- if ((BIGNUM_LENGTH(y)) > (BIGNUM_LENGTH(x))) {
- bignum* z = x;
- x = y;
- y = z;
+ data_root<bignum> x(x_, this);
+ data_root<bignum> y(y_, this);
+
+ if (BIGNUM_LENGTH(y) > BIGNUM_LENGTH(x)) {
+ swap(x, y);
}
{
bignum_digit_type carry;
bignum_digit_type product_low;
bignum_digit_type* scan_r;
bignum_digit_type* scan_y;
- bignum_length_type x_length = (BIGNUM_LENGTH(x));
- bignum_length_type y_length = (BIGNUM_LENGTH(y));
+ bignum_length_type x_length = BIGNUM_LENGTH(x);
+ bignum_length_type y_length = BIGNUM_LENGTH(y);
bignum* r = (allot_bignum_zeroed((x_length + y_length), negative_p));
- bignum_digit_type* scan_x = (BIGNUM_START_PTR(x));
+ bignum_digit_type* scan_x = BIGNUM_START_PTR(x);
bignum_digit_type* end_x = (scan_x + x_length);
- bignum_digit_type* start_y = (BIGNUM_START_PTR(y));
+ bignum_digit_type* start_y = BIGNUM_START_PTR(y);
bignum_digit_type* end_y = (start_y + y_length);
bignum_digit_type* start_r = (BIGNUM_START_PTR(r));
#define x_digit x_digit_high
}
}
-/* Allocates memory */
-bignum* factor_vm::bignum_multiply_unsigned_small_factor(bignum* x,
+// Allocates memory
+bignum* factor_vm::bignum_multiply_unsigned_small_factor(bignum* x_,
bignum_digit_type y,
int negative_p) {
- GC_BIGNUM(x);
+ data_root<bignum> x(x_, this);
bignum_length_type length_x = (BIGNUM_LENGTH(x));
bignum* p = (allot_bignum((length_x + 1), negative_p));
- bignum_destructive_copy(x, p);
+ bignum_destructive_copy(x.untagged(), p);
(BIGNUM_REF(p, length_x)) = 0;
bignum_destructive_scale_up(p, y);
return (bignum_trim(p));
}
-void factor_vm::bignum_destructive_add(bignum* bignum, bignum_digit_type n) {
- bignum_digit_type* scan = (BIGNUM_START_PTR(bignum));
+void factor_vm::bignum_destructive_add(bignum* bn, bignum_digit_type n) {
+ bignum_digit_type* scan = (BIGNUM_START_PTR(bn));
bignum_digit_type digit;
digit = ((*scan) + n);
if (digit < BIGNUM_RADIX) {
}
}
-void factor_vm::bignum_destructive_scale_up(bignum* bignum,
+void factor_vm::bignum_destructive_scale_up(bignum* bn,
bignum_digit_type factor) {
bignum_digit_type carry = 0;
- bignum_digit_type* scan = (BIGNUM_START_PTR(bignum));
+ bignum_digit_type* scan = (BIGNUM_START_PTR(bn));
bignum_digit_type two_digits;
bignum_digit_type product_low;
#define product_high carry
- bignum_digit_type* end = (scan + (BIGNUM_LENGTH(bignum)));
+ bignum_digit_type* end = (scan + (BIGNUM_LENGTH(bn)));
BIGNUM_ASSERT((factor > 1) && (factor < BIGNUM_RADIX_ROOT));
while (scan < end) {
two_digits = (*scan);
(*scan++) = (HD_CONS((HD_LOW(product_high)), (HD_LOW(product_low))));
carry = (HD_HIGH(product_high));
}
- /* A carry here would be an overflow, i.e. it would not fit.
- Hopefully the callers allocate enough space that this will
- never happen.
- */
+ // A carry here would be an overflow, i.e. it would not fit.
+ // Hopefully the callers allocate enough space that this will
+ // never happen.
BIGNUM_ASSERT(carry == 0);
return;
#undef product_high
}
-/* Division */
+// Division
-/* For help understanding this algorithm, see:
- Knuth, Donald E., "The Art of Computer Programming",
- volume 2, "Seminumerical Algorithms"
- section 4.3.1, "Multiple-Precision Arithmetic". */
+// For help understanding this algorithm, see:
+// Knuth, Donald E., "The Art of Computer Programming",
+// volume 2, "Seminumerical Algorithms"
+// section 4.3.1, "Multiple-Precision Arithmetic".
-/* Allocates memory */
+// Allocates memory
void factor_vm::bignum_divide_unsigned_large_denominator(
- bignum* numerator, bignum* denominator, bignum** quotient,
- bignum** remainder, int q_negative_p, int r_negative_p) {
- GC_BIGNUM(numerator);
- GC_BIGNUM(denominator);
+ bignum* numerator_, bignum* denominator_,
+ bignum** quotient, bignum** remainder,
+ int q_negative_p, int r_negative_p) {
- bignum_length_type length_n = ((BIGNUM_LENGTH(numerator)) + 1);
- bignum_length_type length_d = (BIGNUM_LENGTH(denominator));
+ data_root<bignum> numerator(numerator_, this);
+ data_root<bignum> denominator(denominator_, this);
- bignum* q = ((quotient != ((bignum**)0))
- ? (allot_bignum((length_n - length_d), q_negative_p))
- : BIGNUM_OUT_OF_BAND);
- GC_BIGNUM(q);
+ bignum_length_type length_n = BIGNUM_LENGTH(numerator) + 1;
+ bignum_length_type length_d = BIGNUM_LENGTH(denominator);
- bignum* u = (allot_bignum(length_n, r_negative_p));
- GC_BIGNUM(u);
+ data_root<bignum> u(allot_bignum(length_n, r_negative_p), this);
int shift = 0;
BIGNUM_ASSERT(length_d > 1);
{
- bignum_digit_type v1 = (BIGNUM_REF((denominator), (length_d - 1)));
+ bignum_digit_type v1 = BIGNUM_REF(denominator.untagged(), length_d - 1);
while (v1 < (BIGNUM_RADIX / 2)) {
v1 <<= 1;
shift += 1;
}
}
- if (shift == 0) {
- bignum_destructive_copy(numerator, u);
- (BIGNUM_REF(u, (length_n - 1))) = 0;
- bignum_divide_unsigned_normalized(u, denominator, q);
- } else {
- bignum* v = (allot_bignum(length_d, 0));
- bignum_destructive_normalization(numerator, u, shift);
- bignum_destructive_normalization(denominator, v, shift);
- bignum_divide_unsigned_normalized(u, v, q);
- if (remainder != ((bignum**)0))
- bignum_destructive_unnormalization(u, shift);
- }
+ if (quotient != NULL) {
+ bignum *q_ = allot_bignum(length_n - length_d, q_negative_p);
+ data_root<bignum> q(q_, this);
- if (q)
- q = bignum_trim(q);
-
- u = bignum_trim(u);
+ if (shift == 0) {
+ bignum_destructive_copy(numerator.untagged(), u.untagged());
+ (BIGNUM_REF(u.untagged(), (length_n - 1))) = 0;
+ bignum_divide_unsigned_normalized(u.untagged(),
+ denominator.untagged(),
+ q.untagged());
+ } else {
+ bignum* v = allot_bignum(length_d, 0);
+ bignum_destructive_normalization(numerator.untagged(),
+ u.untagged(),
+ shift);
+ bignum_destructive_normalization(denominator.untagged(), v, shift);
+ bignum_divide_unsigned_normalized(u.untagged(), v, q.untagged());
+ if (remainder != NULL)
+ bignum_destructive_unnormalization(u.untagged(), shift);
+ }
- if (quotient != ((bignum**)0))
- (*quotient) = q;
+ q.set_untagged(bignum_trim(q.untagged()));
+ *quotient = q.untagged();
+ } else {
- if (remainder != ((bignum**)0))
- (*remainder) = u;
+ if (shift == 0) {
+ bignum_destructive_copy(numerator.untagged(), u.untagged());
+ (BIGNUM_REF(u.untagged(), (length_n - 1))) = 0;
+ bignum_divide_unsigned_normalized(u.untagged(),
+ denominator.untagged(),
+ NULL);
+ } else {
+ bignum* v = allot_bignum(length_d, 0);
+ bignum_destructive_normalization(numerator.untagged(),
+ u.untagged(),
+ shift);
+ bignum_destructive_normalization(denominator.untagged(),
+ v,
+ shift);
+ bignum_divide_unsigned_normalized(u.untagged(), v, NULL);
+ if (remainder != NULL)
+ bignum_destructive_unnormalization(u.untagged(), shift);
+ }
+ }
- return;
+ u.set_untagged(bignum_trim(u.untagged()));
+ if (remainder != NULL)
+ *remainder = u.untagged();
}
void factor_vm::bignum_divide_unsigned_normalized(bignum* u, bignum* v,
bignum_digit_type* q_scan = NULL;
bignum_digit_type v1 = (v_end[-1]);
bignum_digit_type v2 = (v_end[-2]);
- bignum_digit_type ph; /* high half of double-digit product */
- bignum_digit_type pl; /* low half of double-digit product */
+ bignum_digit_type ph; // high half of double-digit product
+ bignum_digit_type pl; // low half of double-digit product
bignum_digit_type guess;
- bignum_digit_type gh; /* high half-digit of guess */
- bignum_digit_type ch; /* high half of double-digit comparand */
+ bignum_digit_type gh; // high half-digit of guess
+ bignum_digit_type ch; // high half of double-digit comparand
bignum_digit_type v2l = (HD_LOW(v2));
bignum_digit_type v2h = (HD_HIGH(v2));
- bignum_digit_type cl; /* low half of double-digit comparand */
-#define gl ph /* low half-digit of guess */
+ bignum_digit_type cl; // low half of double-digit comparand
+#define gl ph // low half-digit of guess
#define uj pl
#define qj ph
- bignum_digit_type gm; /* memory loc for reference parameter */
+ bignum_digit_type gm; // memory loc for reference parameter
if (q != BIGNUM_OUT_OF_BAND)
q_scan = ((BIGNUM_START_PTR(q)) + (BIGNUM_LENGTH(q)));
while (u_scan_limit < u_scan) {
uj = (*--u_scan);
if (uj != v1) {
- /* comparand =
- (((((uj * BIGNUM_RADIX) + uj1) % v1) * BIGNUM_RADIX) + uj2);
- guess = (((uj * BIGNUM_RADIX) + uj1) / v1); */
+ // comparand =
+ // (((((uj * BIGNUM_RADIX) + uj1) % v1) * BIGNUM_RADIX) + uj2);
+ // guess = (((uj * BIGNUM_RADIX) + uj1) / v1);
cl = (u_scan[-2]);
ch = (bignum_digit_divide(uj, (u_scan[-1]), v1, (&gm)));
guess = gm;
guess = (BIGNUM_RADIX - 1);
}
while (1) {
- /* product = (guess * v2); */
+ // product = (guess * v2);
gl = (HD_LOW(guess));
gh = (HD_HIGH(guess));
pl = (v2l * gl);
ph = ((v2l * gh) + (v2h * gl) + (HD_HIGH(pl)));
pl = (HD_CONS((HD_LOW(ph)), (HD_LOW(pl))));
ph = ((v2h * gh) + (HD_HIGH(ph)));
- /* if (comparand >= product) */
+ // if (comparand >= product)
if ((ch > ph) || ((ch == ph) && (cl >= pl)))
break;
guess -= 1;
- /* comparand += (v1 << BIGNUM_DIGIT_LENGTH) */
+ // comparand += (v1 << BIGNUM_DIGIT_LENGTH)
ch += v1;
- /* if (comparand >= (BIGNUM_RADIX * BIGNUM_RADIX)) */
+ // if (comparand >= (BIGNUM_RADIX * BIGNUM_RADIX))
if (ch >= BIGNUM_RADIX)
break;
}
#undef ph
#undef diff
}
- /* Subtraction generated carry, implying guess is one too large.
- Add v back in to bring it back down. */
+ // Subtraction generated carry, implying guess is one too large.
+ // Add v back in to bring it back down.
v_scan = v_start;
u_scan = u_start;
carry = 0;
return (guess - 1);
}
-/* Allocates memory */
+// Allocates memory
void factor_vm::bignum_divide_unsigned_medium_denominator(
- bignum* numerator, bignum_digit_type denominator, bignum** quotient,
+ bignum* numerator_, bignum_digit_type denominator, bignum** quotient,
bignum** remainder, int q_negative_p, int r_negative_p) {
- GC_BIGNUM(numerator);
+
+ data_root<bignum> numerator(numerator_, this);
bignum_length_type length_n = (BIGNUM_LENGTH(numerator));
- bignum_length_type length_q;
- bignum* q = NULL;
- GC_BIGNUM(q);
int shift = 0;
- /* Because `bignum_digit_divide' requires a normalized denominator. */
+ // Because `bignum_digit_divide' requires a normalized denominator.
while (denominator < (BIGNUM_RADIX / 2)) {
denominator <<= 1;
shift += 1;
}
- if (shift == 0) {
- length_q = length_n;
- q = (allot_bignum(length_q, q_negative_p));
- bignum_destructive_copy(numerator, q);
+ bignum_length_type length_q = (shift == 0) ? length_n : length_n + 1;
+ data_root<bignum> q(allot_bignum(length_q, q_negative_p), this);
+ if (shift == 0) {
+ bignum_destructive_copy(numerator.untagged(), q.untagged());
} else {
- length_q = (length_n + 1);
-
- q = (allot_bignum(length_q, q_negative_p));
- bignum_destructive_normalization(numerator, q, shift);
+ bignum_destructive_normalization(numerator.untagged(), q.untagged(), shift);
}
{
bignum_digit_type r = 0;
(*scan) = qj;
}
- q = bignum_trim(q);
+ q.set_untagged(bignum_trim(q.untagged()));
if (remainder != ((bignum**)0)) {
if (shift != 0)
}
if (quotient != ((bignum**)0))
- (*quotient) = q;
+ (*quotient) = q.untagged();
}
return;
}
bignum_digit_type* end_source = (scan_source + (BIGNUM_LENGTH(source)));
bignum_digit_type* end_target = (scan_target + (BIGNUM_LENGTH(target)));
int shift_right = (BIGNUM_DIGIT_LENGTH - shift_left);
- bignum_digit_type mask = (((cell) 1 << shift_right) - 1);
+ bignum_digit_type mask = (((cell)1 << shift_right) - 1);
while (scan_source < end_source) {
digit = (*scan_source++);
(*scan_target++) = (((digit & mask) << shift_left) | carry);
return;
}
-void factor_vm::bignum_destructive_unnormalization(bignum* bignum,
+void factor_vm::bignum_destructive_unnormalization(bignum* bn,
int shift_right) {
- bignum_digit_type* start = (BIGNUM_START_PTR(bignum));
- bignum_digit_type* scan = (start + (BIGNUM_LENGTH(bignum)));
+ bignum_digit_type* start = (BIGNUM_START_PTR(bn));
+ bignum_digit_type* scan = (start + (BIGNUM_LENGTH(bn)));
bignum_digit_type digit;
bignum_digit_type carry = 0;
int shift_left = (BIGNUM_DIGIT_LENGTH - shift_right);
- bignum_digit_type mask = (((fixnum) 1 << shift_right) - 1);
+ bignum_digit_type mask = (((fixnum)1 << shift_right) - 1);
while (start < scan) {
digit = (*--scan);
(*scan) = ((digit >> shift_right) | carry);
return;
}
-/* This is a reduced version of the division algorithm, applied to the
- case of dividing two bignum digits by one bignum digit. It is
- assumed that the numerator, denominator are normalized. */
+// This is a reduced version of the division algorithm, applied to the
+// case of dividing two bignum digits by one bignum digit. It is
+// assumed that the numerator, denominator are normalized.
#define BDD_STEP(qn, j) \
{ \
bignum_digit_type factor_vm::bignum_digit_divide(
bignum_digit_type uh, bignum_digit_type ul, bignum_digit_type v,
- bignum_digit_type* q) /* return value */
+ bignum_digit_type* q) // return value
{
bignum_digit_type guess;
bignum_digit_type comparand;
#undef BDDS_MULSUB
#undef BDDS_ADD
-/* Allocates memory */
+// Allocates memory
void factor_vm::bignum_divide_unsigned_small_denominator(
- bignum* numerator, bignum_digit_type denominator, bignum** quotient,
+ bignum* numerator_, bignum_digit_type denominator, bignum** quotient,
bignum** remainder, int q_negative_p, int r_negative_p) {
- GC_BIGNUM(numerator);
+ data_root<bignum> numerator(numerator_, this);
- bignum* q = (bignum_new_sign(numerator, q_negative_p));
- GC_BIGNUM(q);
+ bignum* q_ = bignum_new_sign(numerator.untagged(), q_negative_p);
+ data_root<bignum> q(q_, this);
- bignum_digit_type r = (bignum_destructive_scale_down(q, denominator));
+ bignum_digit_type r = bignum_destructive_scale_down(q.untagged(), denominator);
- q = (bignum_trim(q));
+ q.set_untagged(bignum_trim(q.untagged()));
if (remainder != ((bignum**)0))
- (*remainder) = (bignum_digit_to_bignum(r, r_negative_p));
+ (*remainder) = bignum_digit_to_bignum(r, r_negative_p);
- (*quotient) = q;
+ (*quotient) = q.untagged();
return;
}
-/* Given (denominator > 1), it is fairly easy to show that
- (quotient_high < BIGNUM_RADIX_ROOT), after which it is easy to see
- that all digits are < BIGNUM_RADIX. */
+// Given (denominator > 1), it is fairly easy to show that
+// (quotient_high < BIGNUM_RADIX_ROOT), after which it is easy to see
+// that all digits are < BIGNUM_RADIX.
bignum_digit_type factor_vm::bignum_destructive_scale_down(
- bignum* bignum, bignum_digit_type denominator) {
+ bignum* bn, bignum_digit_type denominator) {
bignum_digit_type numerator;
bignum_digit_type remainder = 0;
bignum_digit_type two_digits;
#define quotient_high remainder
- bignum_digit_type* start = (BIGNUM_START_PTR(bignum));
- bignum_digit_type* scan = (start + (BIGNUM_LENGTH(bignum)));
+ bignum_digit_type* start = (BIGNUM_START_PTR(bn));
+ bignum_digit_type* scan = (start + (BIGNUM_LENGTH(bn)));
BIGNUM_ASSERT((denominator > 1) && (denominator < BIGNUM_RADIX_ROOT));
while (start < scan) {
two_digits = (*--scan);
#undef quotient_high
}
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::bignum_remainder_unsigned_small_denominator(
bignum* n, bignum_digit_type d, int negative_p) {
bignum_digit_type two_digits;
return (bignum_digit_to_bignum(r, negative_p));
}
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::bignum_digit_to_bignum(bignum_digit_type digit,
int negative_p) {
if (digit == 0)
}
}
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::allot_bignum(bignum_length_type length, int negative_p) {
BIGNUM_ASSERT((length >= 0) || (length < BIGNUM_RADIX));
bignum* result = allot_uninitialized_array<bignum>(length + 1);
return (result);
}
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::allot_bignum_zeroed(bignum_length_type length,
int negative_p) {
bignum* result = allot_bignum(length, negative_p);
return (result);
}
-/* can allocate if not in nursery or size is larger */
-/* Allocates memory conditionally */
-#define BIGNUM_REDUCE_LENGTH(source, length) \
- source = reallot_array(source, length + 1)
-
-/* Allocates memory */
-bignum* factor_vm::bignum_shorten_length(bignum* bignum,
+// Allocates memory
+bignum* factor_vm::bignum_shorten_length(bignum* bn,
bignum_length_type length) {
- bignum_length_type current_length = (BIGNUM_LENGTH(bignum));
+ bignum_length_type current_length = (BIGNUM_LENGTH(bn));
BIGNUM_ASSERT((length >= 0) || (length <= current_length));
if (length < current_length) {
- GC_BIGNUM(bignum);
- BIGNUM_REDUCE_LENGTH(bignum, length);
- BIGNUM_SET_NEGATIVE_P(bignum, (length != 0) && (BIGNUM_NEGATIVE_P(bignum)));
+ bn = reallot_array(bn, length + 1);
+ BIGNUM_SET_NEGATIVE_P(bn, (length != 0) && (BIGNUM_NEGATIVE_P(bn)));
}
- return (bignum);
+ return (bn);
}
-/* Allocates memory */
-bignum* factor_vm::bignum_trim(bignum* bignum) {
- bignum_digit_type* start = (BIGNUM_START_PTR(bignum));
- bignum_digit_type* end = (start + (BIGNUM_LENGTH(bignum)));
+// Allocates memory
+bignum* factor_vm::bignum_trim(bignum* bn) {
+ bignum_digit_type* start = (BIGNUM_START_PTR(bn));
+ bignum_digit_type* end = (start + (BIGNUM_LENGTH(bn)));
bignum_digit_type* scan = end;
while ((start <= scan) && ((*--scan) == 0))
;
scan += 1;
if (scan < end) {
- GC_BIGNUM(bignum);
bignum_length_type length = (scan - start);
- BIGNUM_REDUCE_LENGTH(bignum, length);
- BIGNUM_SET_NEGATIVE_P(bignum, (length != 0) && (BIGNUM_NEGATIVE_P(bignum)));
+ bn = reallot_array(bn, length + 1);
+ BIGNUM_SET_NEGATIVE_P(bn, (length != 0) && (BIGNUM_NEGATIVE_P(bn)));
}
- return (bignum);
+ return (bn);
}
-/* Copying */
+// Copying
-/* Allocates memory */
-bignum* factor_vm::bignum_new_sign(bignum* x, int negative_p) {
- GC_BIGNUM(x);
- bignum* result = (allot_bignum((BIGNUM_LENGTH(x)), negative_p));
-
- bignum_destructive_copy(x, result);
- return (result);
+// Allocates memory
+bignum* factor_vm::bignum_new_sign(bignum* x_, int negative_p) {
+ data_root<bignum> x(x_, this);
+ bignum* result = allot_bignum(BIGNUM_LENGTH(x), negative_p);
+ bignum_destructive_copy(x.untagged(), result);
+ return result;
}
-/* Allocates memory */
-bignum* factor_vm::bignum_maybe_new_sign(bignum* x, int negative_p) {
- if ((BIGNUM_NEGATIVE_P(x)) ? negative_p : (!negative_p))
- return (x);
+// Allocates memory
+bignum* factor_vm::bignum_maybe_new_sign(bignum* x_, int negative_p) {
+ if ((BIGNUM_NEGATIVE_P(x_)) ? negative_p : (!negative_p))
+ return x_;
else {
- GC_BIGNUM(x);
- bignum* result = (allot_bignum((BIGNUM_LENGTH(x)), negative_p));
- bignum_destructive_copy(x, result);
- return (result);
+ return bignum_new_sign(x_, negative_p);
}
}
return;
}
-/*
- * Added bitwise operations (and oddp).
- */
+// * Added bitwise operations (and oddp).
-/* Allocates memory */
-bignum* factor_vm::bignum_bitwise_not(bignum* x) {
- GC_BIGNUM(x);
+// Allocates memory
+bignum* factor_vm::bignum_bitwise_not(bignum* x_) {
- bignum_length_type size = BIGNUM_LENGTH(x);
- bignum_digit_type* scan_x, *end_x, *scan_y;
- bignum* y;
int carry = 1;
+ bignum_length_type size = BIGNUM_LENGTH(x_);
+ int is_negative = BIGNUM_NEGATIVE_P(x_);
+ data_root<bignum> x(x_, this);
+ data_root<bignum> y(allot_bignum(size, is_negative ? 0 : 1), this);
+
+ bignum_digit_type* scan_x = BIGNUM_START_PTR(x);
+ bignum_digit_type* end_x = scan_x + size;
+ bignum_digit_type* scan_y = BIGNUM_START_PTR(y);
- if (BIGNUM_NEGATIVE_P(x)) {
- y = allot_bignum(size, 0);
- scan_x = BIGNUM_START_PTR(x);
- end_x = scan_x + size;
- scan_y = BIGNUM_START_PTR(y);
+ if (is_negative) {
while (scan_x < end_x) {
if (*scan_x == 0) {
*scan_y++ = BIGNUM_RADIX - 1;
}
}
} else {
- y = allot_bignum(size, 1);
- scan_x = BIGNUM_START_PTR(x);
- end_x = scan_x + size;
- scan_y = BIGNUM_START_PTR(y);
while (scan_x < end_x) {
if (*scan_x == (BIGNUM_RADIX - 1)) {
*scan_y++ = 0;
}
if (carry) {
- GC_BIGNUM(y);
- x = allot_bignum(size + 1, BIGNUM_NEGATIVE_P(y));
- bignum_destructive_copy(y, x);
- scan_x = BIGNUM_START_PTR(x);
- *(scan_x + size) = 1;
- return x;
+ bignum* ret = allot_bignum(size + 1, BIGNUM_NEGATIVE_P(y));
+ bignum_destructive_copy(y.untagged(), ret);
+ bignum_digit_type* ret_start = BIGNUM_START_PTR(ret);
+ *(ret_start + size) = 1;
+ return ret;
} else {
- return bignum_trim(y);
+ return bignum_trim(y.untagged());
}
}
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::bignum_arithmetic_shift(bignum* arg1, fixnum n) {
if (BIGNUM_NEGATIVE_P(arg1) && n < 0)
return bignum_bitwise_not(
#define IOR_OP 1
#define XOR_OP 2
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::bignum_bitwise_and(bignum* arg1, bignum* arg2) {
return ((BIGNUM_NEGATIVE_P(arg1)) ? (BIGNUM_NEGATIVE_P(arg2))
? bignum_negneg_bitwise_op(AND_OP, arg1, arg2)
: bignum_pospos_bitwise_op(AND_OP, arg1, arg2));
}
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::bignum_bitwise_ior(bignum* arg1, bignum* arg2) {
return ((BIGNUM_NEGATIVE_P(arg1)) ? (BIGNUM_NEGATIVE_P(arg2))
? bignum_negneg_bitwise_op(IOR_OP, arg1, arg2)
: bignum_pospos_bitwise_op(IOR_OP, arg1, arg2));
}
-/* Allocates memory */
+// Allocates memory
bignum* factor_vm::bignum_bitwise_xor(bignum* arg1, bignum* arg2) {
return ((BIGNUM_NEGATIVE_P(arg1)) ? (BIGNUM_NEGATIVE_P(arg2))
? bignum_negneg_bitwise_op(XOR_OP, arg1, arg2)
: bignum_pospos_bitwise_op(XOR_OP, arg1, arg2));
}
-/* Allocates memory */
-/* ash for the magnitude */
-/* assume arg1 is a big number, n is a long */
-bignum* factor_vm::bignum_magnitude_ash(bignum* arg1, fixnum n) {
- GC_BIGNUM(arg1);
+// Allocates memory
+// ash for the magnitude
+// assume arg1 is a big number, n is a long
+bignum* factor_vm::bignum_magnitude_ash(bignum* arg1_, fixnum n) {
+
+ data_root<bignum> arg1(arg1_, this);
bignum* result = NULL;
bignum_digit_type* scan1;
fixnum digit_offset, bit_offset;
if (BIGNUM_ZERO_P(arg1))
- return (arg1);
+ return arg1.untagged();
if (n > 0) {
digit_offset = n / BIGNUM_DIGIT_LENGTH;
*scanr = *scanr & BIGNUM_DIGIT_MASK;
}
} else if (n < 0 && (-n >= (BIGNUM_LENGTH(arg1) * (bignum_length_type)
- BIGNUM_DIGIT_LENGTH)))
+ BIGNUM_DIGIT_LENGTH))) {
result = BIGNUM_ZERO();
-
- else if (n < 0) {
+ } else if (n < 0) {
digit_offset = -n / BIGNUM_DIGIT_LENGTH;
bit_offset = -n % BIGNUM_DIGIT_LENGTH;
scanr++;
}
*scanr = (*scan1++ & BIGNUM_DIGIT_MASK) >> bit_offset;
- } else if (n == 0)
- result = arg1;
+ } else if (n == 0) {
+ result = arg1.untagged();
+ }
- return (bignum_trim(result));
+ return bignum_trim(result);
}
-/* Allocates memory */
-bignum* factor_vm::bignum_pospos_bitwise_op(int op, bignum* arg1,
- bignum* arg2) {
- GC_BIGNUM(arg1);
- GC_BIGNUM(arg2);
+// Allocates memory
+bignum* factor_vm::bignum_pospos_bitwise_op(int op, bignum* arg1_,
+ bignum* arg2_) {
+ data_root<bignum> arg1(arg1_, this);
+ data_root<bignum> arg2(arg2_, this);
- bignum* result;
bignum_length_type max_length;
bignum_digit_type* scan1, *end1, digit1;
(BIGNUM_LENGTH(arg1) > BIGNUM_LENGTH(arg2)) ? BIGNUM_LENGTH(arg1)
: BIGNUM_LENGTH(arg2);
- result = allot_bignum(max_length, 0);
+ bignum* result = allot_bignum(max_length, 0);
scanr = BIGNUM_START_PTR(result);
scan1 = BIGNUM_START_PTR(arg1);
return bignum_trim(result);
}
-/* Allocates memory */
-bignum* factor_vm::bignum_posneg_bitwise_op(int op, bignum* arg1,
- bignum* arg2) {
- GC_BIGNUM(arg1);
- GC_BIGNUM(arg2);
+// Allocates memory
+bignum* factor_vm::bignum_posneg_bitwise_op(int op, bignum* arg1_,
+ bignum* arg2_) {
+ data_root<bignum> arg1(arg1_, this);
+ data_root<bignum> arg2(arg2_, this);
- bignum* result;
bignum_length_type max_length;
bignum_digit_type* scan1, *end1, digit1;
(BIGNUM_LENGTH(arg1) > BIGNUM_LENGTH(arg2) + 1) ? BIGNUM_LENGTH(arg1)
: BIGNUM_LENGTH(arg2) + 1;
- result = allot_bignum(max_length, neg_p);
+ bignum* result = allot_bignum(max_length, neg_p);
scanr = BIGNUM_START_PTR(result);
scan1 = BIGNUM_START_PTR(arg1);
return bignum_trim(result);
}
-/* Allocates memory */
-bignum* factor_vm::bignum_negneg_bitwise_op(int op, bignum* arg1,
- bignum* arg2) {
- GC_BIGNUM(arg1);
- GC_BIGNUM(arg2);
+// Allocates memory
+bignum* factor_vm::bignum_negneg_bitwise_op(int op, bignum* arg1_,
+ bignum* arg2_) {
+ data_root<bignum> arg1(arg1_, this);
+ data_root<bignum> arg2(arg2_, this);
- bignum* result;
bignum_length_type max_length;
bignum_digit_type* scan1, *end1, digit1, carry1;
(BIGNUM_LENGTH(arg1) > BIGNUM_LENGTH(arg2)) ? BIGNUM_LENGTH(arg1) + 1
: BIGNUM_LENGTH(arg2) + 1;
- result = allot_bignum(max_length, neg_p);
+ bignum* result = allot_bignum(max_length, neg_p);
scanr = BIGNUM_START_PTR(result);
scan1 = BIGNUM_START_PTR(arg1);
}
}
-/* Allocates memory */
-bignum* factor_vm::bignum_integer_length(bignum* x) {
- GC_BIGNUM(x);
-
+// Allocates memory
+bignum* factor_vm::bignum_integer_length(bignum* x_) {
+ data_root<bignum> x(x_, this);
bignum_length_type index = ((BIGNUM_LENGTH(x)) - 1);
bignum_digit_type digit = (BIGNUM_REF(x, index));
+ bignum_digit_type carry = 0;
+ bignum* result;
- bignum* result = (allot_bignum(2, 0));
-
- (BIGNUM_REF(result, 0)) = index;
- (BIGNUM_REF(result, 1)) = 0;
- bignum_destructive_scale_up(result, BIGNUM_DIGIT_LENGTH);
while (digit > 1) {
- bignum_destructive_add(result, ((bignum_digit_type) 1));
+ carry += 1;
digit >>= 1;
}
+
+ if (index < BIGNUM_RADIX_ROOT) {
+ result = allot_bignum(1, 0);
+ (BIGNUM_REF(result, 0)) = (index * BIGNUM_DIGIT_LENGTH) + carry;
+ } else {
+ result = allot_bignum(2, 0);
+ (BIGNUM_REF(result, 0)) = index;
+ (BIGNUM_REF(result, 1)) = 0;
+ bignum_destructive_scale_up(result, BIGNUM_DIGIT_LENGTH);
+ bignum_destructive_add(result, carry);
+ }
return (bignum_trim(result));
}
-/* Allocates memory */
+// Allocates memory
int factor_vm::bignum_logbitp(int shift, bignum* arg) {
return ((BIGNUM_NEGATIVE_P(arg))
? !bignum_unsigned_logbitp(shift, bignum_bitwise_not(arg))
: bignum_unsigned_logbitp(shift, arg));
}
-int factor_vm::bignum_unsigned_logbitp(int shift, bignum* bignum) {
- bignum_length_type len = (BIGNUM_LENGTH(bignum));
+int factor_vm::bignum_unsigned_logbitp(int shift, bignum* bn) {
+ bignum_length_type len = (BIGNUM_LENGTH(bn));
int index = shift / BIGNUM_DIGIT_LENGTH;
if (index >= len)
return 0;
- bignum_digit_type digit = (BIGNUM_REF(bignum, index));
+ bignum_digit_type digit = (BIGNUM_REF(bn, index));
int p = shift % BIGNUM_DIGIT_LENGTH;
- bignum_digit_type mask = ((fixnum) 1) << p;
+ bignum_digit_type mask = ((fixnum)1) << p;
return (digit & mask) ? 1 : 0;
}
#ifdef _WIN64
-/* Allocates memory */
-bignum* factor_vm::bignum_gcd(bignum* a, bignum* b) {
- GC_BIGNUM(a);
- GC_BIGNUM(b);
- bignum* d;
- bignum_length_type size_a, size_b;
- bignum_digit_type* scan_a, *scan_b, *scan_d, *a_end, *b_end;
-
- if (BIGNUM_NEGATIVE_P(a)) {
- size_a = BIGNUM_LENGTH(a);
- d = allot_bignum(size_a, 0);
- scan_d = BIGNUM_START_PTR(d);
- scan_a = BIGNUM_START_PTR(a);
- a_end = scan_a + size_a;
- while (scan_a < a_end)
- (*scan_d++) = (*scan_a++);
- a = d;
- }
+// Allocates memory.
+bignum* factor_vm::bignum_gcd(bignum* a_, bignum* b_) {
- if (BIGNUM_NEGATIVE_P(b)) {
- size_b = BIGNUM_LENGTH(b);
- d = allot_bignum(size_b, 0);
- scan_d = BIGNUM_START_PTR(d);
- scan_b = BIGNUM_START_PTR(b);
- b_end = scan_b + size_b;
- while (scan_b < b_end)
- (*scan_d++) = (*scan_b++);
- b = d;
- }
+ data_root<bignum> a(a_, this);
+ data_root<bignum> b(b_, this);
+
+ // Copies of a and b with that are both positive.
+ data_root<bignum> ac(bignum_maybe_new_sign(a.untagged(), 0), this);
+ data_root<bignum> bc(bignum_maybe_new_sign(b.untagged(), 0), this);
- if (bignum_compare(a, b) == bignum_comparison_less) {
- std::swap(a, b);
+ if (bignum_compare(ac.untagged(), bc.untagged()) == BIGNUM_COMPARISON_LESS) {
+ swap(ac, bc);
}
- while (BIGNUM_LENGTH(b) != 0) {
- d = bignum_remainder(a, b);
- GC_BIGNUM(d);
- if (d == BIGNUM_OUT_OF_BAND) {
- return d;
+ while (BIGNUM_LENGTH(bc) != 0) {
+ data_root<bignum> d(bignum_remainder(ac.untagged(), bc.untagged()), this);
+ if (d.untagged() == BIGNUM_OUT_OF_BAND) {
+ return d.untagged();
}
- a = b;
- b = d;
+ ac = bc;
+ bc = d;
}
-
- return a;
+ return ac.untagged();
}
#else
-/* Allocates memory */
-bignum* factor_vm::bignum_gcd(bignum* a, bignum* b) {
- GC_BIGNUM(a);
- GC_BIGNUM(b);
- bignum* c, *d, *e, *f;
+// Allocates memory
+bignum* factor_vm::bignum_gcd(bignum* a_, bignum* b_) {
+ data_root<bignum> a(a_, this);
+ data_root<bignum> b(b_, this);
bignum_twodigit_type x, y, q, s, t, A, B, C, D;
- int nbits, k;
+ unsigned long nbits;
+ int k;
bignum_length_type size_a, size_b, size_c;
bignum_digit_type* scan_a, *scan_b, *scan_c, *scan_d;
bignum_digit_type* a_end, *b_end, *c_end;
- /* clone the bignums so we can modify them in-place */
+ // clone the bignums so we can modify them in-place
size_a = BIGNUM_LENGTH(a);
- c = allot_bignum(size_a, 0);
+ data_root<bignum> c(allot_bignum(size_a, 0), this);
+ // c = allot_bignum(size_a, 0);
scan_a = BIGNUM_START_PTR(a);
a_end = scan_a + size_a;
- GC_BIGNUM(c);
scan_c = BIGNUM_START_PTR(c);
while (scan_a < a_end)
(*scan_c++) = (*scan_a++);
a = c;
size_b = BIGNUM_LENGTH(b);
- d = allot_bignum(size_b, 0);
+ data_root<bignum> d(allot_bignum(size_b, 0), this);
scan_b = BIGNUM_START_PTR(b);
b_end = scan_b + size_b;
- GC_BIGNUM(d);
scan_d = BIGNUM_START_PTR(d);
while (scan_b < b_end)
(*scan_d++) = (*scan_b++);
b = d;
- /* Initial reduction: make sure that 0 <= b <= a. */
- if (bignum_compare(a, b) == bignum_comparison_less) {
- std::swap(a, b);
+ // Initial reduction: make sure that 0 <= b <= a.
+ if (bignum_compare(a.untagged(), b.untagged()) == BIGNUM_COMPARISON_LESS) {
+ swap(a, b);
std::swap(size_a, size_b);
}
? BIGNUM_REF(b, size_a - 1) << (BIGNUM_DIGIT_LENGTH - nbits)
: 0));
- /* inner loop of Lehmer's algorithm; */
+ // inner loop of Lehmer's algorithm;
A = 1;
B = 0;
C = 0;
}
if (k == 0) {
- /* no progress; do a Euclidean step */
+ // no progress; do a Euclidean step
if (size_b == 0) {
- return bignum_trim(a);
+ return bignum_trim(a.untagged());
}
- e = bignum_trim(a);
- GC_BIGNUM(e);
- f = bignum_trim(b);
- GC_BIGNUM(f);
- c = bignum_remainder(e, f);
- GC_BIGNUM(c);
- if (c == BIGNUM_OUT_OF_BAND) {
- return c;
+ data_root<bignum> e(bignum_trim(a.untagged()), this);
+ data_root<bignum> f(bignum_trim(b.untagged()), this);
+ c.set_untagged(bignum_remainder(e.untagged(), f.untagged()));
+ if (c.untagged() == BIGNUM_OUT_OF_BAND) {
+ return c.untagged();
}
// copy 'b' to 'a'
continue;
}
- /*
- a, b = A*b - B*a, D*a - C*b if k is odd
- a, b = A*a - B*b, D*b - C*a if k is even
- */
+ // a, b = A*b - B*a, D*a - C*b if k is odd
+ // a, b = A*a - B*b, D*b - C*a if k is even
+
scan_a = BIGNUM_START_PTR(a);
scan_b = BIGNUM_START_PTR(b);
scan_c = scan_a;
BIGNUM_ASSERT(size_a >= size_b);
}
- /* a fits into a fixnum, so b must too */
- fixnum xx = bignum_to_fixnum(a);
- fixnum yy = bignum_to_fixnum(b);
+ // a fits into a fixnum, so b must too
+ fixnum xx = bignum_to_fixnum(a.untagged());
+ fixnum yy = bignum_to_fixnum(b.untagged());
fixnum tt;
- /* usual Euclidean algorithm for longs */
+ // usual Euclidean algorithm for longs
while (yy != 0) {
tt = yy;
yy = xx % yy;
projects / factor.git / blobdiff