429
long_to_bignum (long n)
432
bignum_digit_type result_digits [BIGNUM_DIGITS_FOR_LONG];
433
bignum_digit_type * end_digits = result_digits;
434
/* Special cases win when these small constants are cached. */
435
if (n == 0) return (BIGNUM_ZERO ());
436
if (n == 1) return (BIGNUM_ONE (0));
437
if (n == -1) return (BIGNUM_ONE (1));
439
unsigned long accumulator = ((negative_p = (n < 0)) ? (-n) : n);
442
(*end_digits++) = (accumulator & BIGNUM_DIGIT_MASK);
443
accumulator >>= BIGNUM_DIGIT_LENGTH;
445
while (accumulator != 0);
449
(bignum_allocate ((end_digits - result_digits), negative_p));
450
bignum_digit_type * scan_digits = result_digits;
451
bignum_digit_type * scan_result = (BIGNUM_START_PTR (result));
452
while (scan_digits < end_digits)
453
(*scan_result++) = (*scan_digits++);
459
bignum_to_long (bignum_type bignum)
461
if (BIGNUM_ZERO_P (bignum))
464
unsigned long accumulator = 0;
465
bignum_digit_type * start = (BIGNUM_START_PTR (bignum));
466
bignum_digit_type * scan = (start + (BIGNUM_LENGTH (bignum)));
468
accumulator = ((accumulator << BIGNUM_DIGIT_LENGTH) + (*--scan));
470
((BIGNUM_NEGATIVE_P (bignum))
471
? (- ((long) accumulator))
472
: ((long) accumulator));
477
ulong_to_bignum (unsigned long n)
479
bignum_digit_type result_digits [BIGNUM_DIGITS_FOR_LONG];
480
bignum_digit_type * end_digits = result_digits;
481
/* Special cases win when these small constants are cached. */
482
if (n == 0) return (BIGNUM_ZERO ());
483
if (n == 1) return (BIGNUM_ONE (0));
485
unsigned long accumulator = n;
488
(*end_digits++) = (accumulator & BIGNUM_DIGIT_MASK);
489
accumulator >>= BIGNUM_DIGIT_LENGTH;
491
while (accumulator != 0);
495
(bignum_allocate ((end_digits - result_digits), 0));
496
bignum_digit_type * scan_digits = result_digits;
497
bignum_digit_type * scan_result = (BIGNUM_START_PTR (result));
498
while (scan_digits < end_digits)
499
(*scan_result++) = (*scan_digits++);
505
bignum_to_ulong (bignum_type bignum)
507
if (BIGNUM_ZERO_P (bignum))
509
BIGNUM_ASSERT (BIGNUM_POSITIVE_P (bignum));
511
unsigned long accumulator = 0;
512
bignum_digit_type * start = (BIGNUM_START_PTR (bignum));
513
bignum_digit_type * scan = (start + (BIGNUM_LENGTH (bignum)));
515
accumulator = ((accumulator << BIGNUM_DIGIT_LENGTH) + (*--scan));
516
return (accumulator);
423
bignum_from_digits (bignum_digit_type *start_digits,
424
bignum_digit_type *end_digits,
428
(bignum_allocate ((end_digits - start_digits), negative_p));
429
bignum_digit_type *scan_digits = start_digits;
430
bignum_digit_type *scan_result = (BIGNUM_START_PTR (result));
431
while (scan_digits < end_digits)
432
(*scan_result++) = (*scan_digits++);
436
#define DEFINE_INT_TO_BIGNUM(NAME, TYPE, UTYPE) \
440
/* Special cases win when these small constants are cached. */ \
441
if (n == 0) return (BIGNUM_ZERO ()); \
442
if (n == 1) return (BIGNUM_ONE (0)); \
443
if (n == -1) return (BIGNUM_ONE (1)); \
446
bignum_digit_type result_digits [BIGNUM_DIGITS_FOR_TYPE (TYPE)]; \
447
bignum_digit_type * end_digits = result_digits; \
448
UTYPE accumulator = ((negative_p = (n < 0)) ? (-n) : n); \
450
(*end_digits++) = (accumulator & BIGNUM_DIGIT_MASK); \
451
accumulator >>= BIGNUM_DIGIT_LENGTH; \
452
} while (accumulator != 0); \
454
(bignum_from_digits (result_digits, end_digits, negative_p)); \
458
DEFINE_INT_TO_BIGNUM (long_to_bignum, long, unsigned long)
459
DEFINE_INT_TO_BIGNUM (intmax_to_bignum, intmax_t, uintmax_t)
461
#define DEFINE_BIGNUM_TO_INT(NAME, TYPE, UTYPE) \
463
NAME (bignum_type bignum) \
465
if (BIGNUM_ZERO_P (bignum)) \
468
UTYPE accumulator = 0; \
469
bignum_digit_type * start = (BIGNUM_START_PTR (bignum)); \
470
bignum_digit_type * scan = (start + (BIGNUM_LENGTH (bignum))); \
471
while (start < scan) \
472
accumulator = ((accumulator << BIGNUM_DIGIT_LENGTH) + (*--scan)); \
474
((BIGNUM_NEGATIVE_P (bignum)) \
475
? (- ((TYPE) accumulator)) \
476
: ((TYPE) accumulator)); \
480
DEFINE_BIGNUM_TO_INT (bignum_to_long, long, unsigned long)
481
DEFINE_BIGNUM_TO_INT (bignum_to_intmax, intmax_t, uintmax_t)
483
#define DEFINE_UINT_TO_BIGNUM(NAME, TYPE) \
487
/* Special cases win when these small constants are cached. */ \
488
if (n == 0) return (BIGNUM_ZERO ()); \
489
if (n == 1) return (BIGNUM_ONE (0)); \
491
bignum_digit_type result_digits [BIGNUM_DIGITS_FOR_TYPE (TYPE)]; \
492
bignum_digit_type * end_digits = result_digits; \
493
TYPE accumulator = n; \
495
(*end_digits++) = (accumulator & BIGNUM_DIGIT_MASK); \
496
accumulator >>= BIGNUM_DIGIT_LENGTH; \
497
} while (accumulator != 0); \
498
return (bignum_from_digits (result_digits, end_digits, false)); \
502
DEFINE_UINT_TO_BIGNUM (ulong_to_bignum, unsigned long)
503
DEFINE_UINT_TO_BIGNUM (uintmax_to_bignum, uintmax_t)
505
#define DEFINE_BIGNUM_TO_UINT(NAME, TYPE) \
507
NAME (bignum_type bignum) \
509
if (BIGNUM_ZERO_P (bignum)) \
511
BIGNUM_ASSERT (BIGNUM_POSITIVE_P (bignum)); \
513
TYPE accumulator = 0; \
514
bignum_digit_type * start = (BIGNUM_START_PTR (bignum)); \
515
bignum_digit_type * scan = (start + (BIGNUM_LENGTH (bignum))); \
516
while (start < scan) \
517
accumulator = ((accumulator << BIGNUM_DIGIT_LENGTH) + (*--scan)); \
518
return (accumulator); \
522
DEFINE_BIGNUM_TO_UINT (bignum_to_ulong, unsigned long)
523
DEFINE_BIGNUM_TO_UINT (bignum_to_uintmax, uintmax_t)
520
525
#define DTB_WRITE_DIGIT(n_bits) do \
776
/* All these bitwise operations are complicated because they interpret
777
integers as their two's-complement representations, whereas bignums
778
are stored in a ones-complement representation. */
781
bignum_bitwise_not (bignum_type bignum)
783
return (bignum_subtract ((BIGNUM_ONE (1)), bignum));
786
#define DEFINE_BITWISE_UNSIGNED(NAME, COMMUTE, OP, POSTOP) \
788
NAME (bignum_type x, bignum_type y) \
790
if ((BIGNUM_LENGTH (x)) < (BIGNUM_LENGTH (y))) \
793
bignum_length_type x_length = (BIGNUM_LENGTH (x)); \
794
bignum_length_type y_length = (BIGNUM_LENGTH (y)); \
795
bignum_length_type r_length = x_length; \
796
bignum_type r = (bignum_allocate (r_length, 0)); \
797
bignum_digit_type *x_scan = (BIGNUM_START_PTR (x)); \
798
bignum_digit_type *x_end = (x_scan + x_length); \
799
bignum_digit_type *y_scan = (BIGNUM_START_PTR (y)); \
800
bignum_digit_type *y_end = (y_scan + y_length); \
801
bignum_digit_type *r_scan = (BIGNUM_START_PTR (r)); \
802
BIGNUM_ASSERT (x_length >= y_length); \
803
while (y_scan < y_end) \
804
(*r_scan++) = (BITWISE_##OP ((*x_scan++), (*y_scan++))); \
805
while (x_scan < x_end) \
806
(*r_scan++) = (BITWISE_##OP ((*x_scan++), 0)); \
807
return (POSTOP (bignum_trim (r))); \
811
#define BITWISE_AND(x, y) ((x) & (y))
812
#define BITWISE_ANDC2(x, y) ((x) &~ (y))
813
#define BITWISE_ANDC1(x, y) ((y) &~ (x))
814
#define BITWISE_XOR(x, y) ((x) ^ (y))
815
#define BITWISE_IOR(x, y) ((x) | (y))
817
/* These don't work, because they set the high bits. */
818
/* #define BITWISE_ORC2(x, y) (BIGNUM_DIGIT_MASK & ((x) |~ (y))) */
819
/* #define BITWISE_ORC1(x, y) (BIGNUM_DIGIT_MASK & ((y) |~ (x))) */
821
/* Kludgey syntactic hack! */
822
#define COMMUTE(name) return bignum_bitwise_##name##_unsigned
823
#define SWAP(x, y) do { bignum_type t = x; x = y; y = t; } while (0)
825
static bignum_type bignum_bitwise_andc1_unsigned (bignum_type, bignum_type);
826
static bignum_type bignum_bitwise_orc1_unsigned (bignum_type, bignum_type);
828
/* These definitions are ordered by their truth tables. */
830
/* DEFINE_BITWISE_UNSIGNED (bignum_bitwise_clear_unsigned, SWAP, CLEAR,) */
831
DEFINE_BITWISE_UNSIGNED (bignum_bitwise_and_unsigned, SWAP, AND,)
832
DEFINE_BITWISE_UNSIGNED (bignum_bitwise_andc2_unsigned, COMMUTE(andc1), ANDC2,)
833
/* DEFINE_BITWISE_UNSIGNED (bignum_bitwise_arg1_unsigned, COMMUTE(ARG2), ARG1,) */
834
DEFINE_BITWISE_UNSIGNED (bignum_bitwise_andc1_unsigned, COMMUTE(andc2), ANDC1,)
835
/* DEFINE_BITWISE_UNSIGNED (bignum_bitwise_arg2_unsigned, ARG2,) */
836
DEFINE_BITWISE_UNSIGNED (bignum_bitwise_xor_unsigned, SWAP, XOR,)
837
DEFINE_BITWISE_UNSIGNED (bignum_bitwise_ior_unsigned, SWAP, IOR,)
838
DEFINE_BITWISE_UNSIGNED (bignum_bitwise_nor_unsigned, SWAP, IOR, bignum_bitwise_not)
839
DEFINE_BITWISE_UNSIGNED (bignum_bitwise_eqv_unsigned, SWAP, XOR, bignum_bitwise_not)
840
/* DEFINE_BITWISE_UNSIGNED (bignum_bitwise_not2_unsigned, COMMUTE(not1), ARG1, bignum_bitwise_not) */
841
/* DEFINE_BITWISE_UNSIGNED (bignum_bitwise_orc2_unsigned, COMMUTE(orc1), ORC2,) */
842
/* DEFINE_BITWISE_UNSIGNED (bignum_bitwise_not1_unsigned, COMMUTE(not1), ARG2, bignum_bitwise_not) */
843
/* DEFINE_BITWISE_UNSIGNED (bignum_bitwise_orc1_unsigned, COMMUTE(orc2), ORC2,) */
844
DEFINE_BITWISE_UNSIGNED (bignum_bitwise_nand_unsigned, SWAP, AND, bignum_bitwise_not)
845
/* DEFINE_BITWISE_UNSIGNED (bignum_bitwise_set_unsigned, SWAP, CLEAR, bignum_bitwise_not) */
848
bignum_bitwise_orc2_unsigned (bignum_type x, bignum_type y)
850
return (bignum_bitwise_not (bignum_bitwise_andc1 (x, y)));
854
bignum_bitwise_orc1_unsigned (bignum_type x, bignum_type y)
856
return (bignum_bitwise_not (bignum_bitwise_andc2 (x, y)));
861
#undef DEFINE_BITWISE_UNSIGNED
863
#define DEFINE_BITWISE(NAME, X0, Y0, PP, PN, NP, NN) \
865
NAME (bignum_type x, bignum_type y) \
867
if (BIGNUM_ZERO_P (x)) return (Y0); \
868
if (BIGNUM_ZERO_P (y)) return (X0); \
870
((BIGNUM_POSITIVE_P (x)) \
871
? ((BIGNUM_POSITIVE_P (y)) \
872
? (bignum_bitwise_##PP##_unsigned (x, y)) \
873
: (bignum_bitwise_##PN##_unsigned (x, (bignum_bitwise_not (y))))) \
874
: ((BIGNUM_POSITIVE_P (y)) \
875
? (bignum_bitwise_##NP##_unsigned ((bignum_bitwise_not (x)), y)) \
876
: (bignum_bitwise_##NN##_unsigned \
877
((bignum_bitwise_not (x)), (bignum_bitwise_not (y)))))); \
880
DEFINE_BITWISE (bignum_bitwise_and, (BIGNUM_ZERO ()), (BIGNUM_ZERO ()),
881
and, andc2, andc1, nor)
883
DEFINE_BITWISE (bignum_bitwise_andc2, x, (BIGNUM_ZERO ()),
884
andc2, and, nor, andc1)
886
DEFINE_BITWISE (bignum_bitwise_andc1, (BIGNUM_ZERO ()), y,
887
andc1, nor, and, andc2)
889
DEFINE_BITWISE (bignum_bitwise_xor, x, y, xor, eqv, eqv, xor)
891
DEFINE_BITWISE (bignum_bitwise_ior, x, y, ior, orc2, orc1, nand)
893
DEFINE_BITWISE (bignum_bitwise_nor,
894
(bignum_bitwise_not (x)),
895
(bignum_bitwise_not (y)),
896
nor, andc1, andc2, and)
898
DEFINE_BITWISE (bignum_bitwise_eqv,
899
(bignum_bitwise_not (x)),
900
(bignum_bitwise_not (y)),
903
DEFINE_BITWISE (bignum_bitwise_orc2,
904
(BIGNUM_ONE (1)), (bignum_bitwise_not (y)),
905
orc2, ior, nand, orc1)
907
DEFINE_BITWISE (bignum_bitwise_orc1,
908
(bignum_bitwise_not (x)), (BIGNUM_ONE (1)),
909
orc1, nand, ior, orc2)
911
DEFINE_BITWISE (bignum_bitwise_nand, (BIGNUM_ONE (1)), (BIGNUM_ONE (1)),
912
nand, orc1, orc2, ior)
914
#undef DEFINE_BITWISE
916
/* General bit-twiddlers. */
918
/* (edit a a-pos b b-pos selector size)
919
= (ior (and a (shift-left selector a-pos))
920
(shift-left (and (shift-right b b-pos) (not selector)) a-pos))
922
In other words, replace a[a-pos + i] by b[b-pos + i] if selector[i]
923
is zero, and shift the result right by pos (which can be negative).
924
For example, (extract size pos x) = (edit x pos 0 0 (mask size 0)). */
928
bignum_edit_bit_field (bignum_type x, unsigned long x_position,
929
bignum_type y, unsigned long y_position,
930
bignum_type selector, unsigned long size)
932
BIGNUM_ASSERT (!BIGNUM_NEGATIVE_P (x));
933
BIGNUM_ASSERT (!BIGNUM_NEGATIVE_P (y));
934
BIGNUM_ASSERT (!BIGNUM_NEGATIVE_P (selector));
935
if (BIGNUM_ZERO_P (selector))
938
bignum_length_type x_length = (BIGNUM_LENGTH (x));
939
bignum_length_type y_length = (BIGNUM_LENGTH (y));
940
bignum_length_type selector_length = (BIGNUM_LENGTH (selector));
941
bignum_length_type r_length = (MAX (x_length, (y_position + size)));
942
bignum_type r = (bignum_allocate (r_length, (BIGNUM_NEGATIVE_P (x))));
943
bignum_length_type x_digit_position = (x_position / BIGNUM_DIGIT_LENGTH);
944
bignum_length_type y_digit_position = (y_position / BIGNUM_DIGIT_LENGTH);
945
bignum_length_type x_bit_position = (x_position % BIGNUM_DIGIT_LENGTH);
946
bignum_length_type y_bit_position = (y_position % BIGNUM_DIGIT_LENGTH);
947
bignum_digit_type *x_scan = (BIGNUM_START_PTR (x));
948
bignum_digit_type *y_scan = (BIGNUM_START_PTR (y));
949
bignum_digit_type *selector_scan = (BIGNUM_START_PTR (selector));
950
bignum_digit_type *r_scan = (BIGNUM_START_PTR (r));
951
bignum_digit_type *x_end = (x_scan + x_length);
952
bignum_digit_type *y_end = (y_scan + y_length);
953
bignum_digit_type *selector_end = (selector_scan + selector_length);
955
bignum_digit_type *stop = (x_scan + (MIN (x_digit_position, x_length)));
956
while (x_scan < stop)
957
(*r_scan++) = (*x_scan++);
959
/* Four cases to deal with, depending on whether or not x and y
961
y_scan += (MIN (y_digit_position, (y_end - y_scan)));
962
if ((x_scan < x_end) && (y_scan < y_end))
964
bignum_digit_type x_low_mask = (BIGNUM_DIGIT_ONES (x_bit_position));
965
bignum_digit_type x_high_mask
966
= (BIGNUM_DIGIT_ONES (BIGNUM_DIGIT_LENGTH - x_bit_position));
967
bignum_digit_type y_low_mask = (BIGNUM_DIGIT_ONES (y_bit_position));
968
bignum_digit_type y_high_mask
969
= (BIGNUM_DIGIT_ONES (BIGNUM_DIGIT_LENGTH - y_bit_position));
970
bignum_digit_type r_carry = ((*x_scan) & x_low_mask);
971
bignum_digit_type x_carry
972
= (((*x_scan++) >> x_bit_position) & x_high_mask);
973
bignum_digit_type y_carry
974
= (((*y_scan++) >> y_bit_position) & y_high_mask);
975
while ((x_scan < x_end) && (y_scan < y_end))
977
bignum_digit_type selector = (*selector_scan++);
978
bignum_digit_type x = (*x_scan++);
979
bignum_digit_type y = (*y_scan++);
982
| ((x_carry ) << x_bit_position)
985
| ((((x >> x_bit_position) & x_high_mask &~ selector)
986
| (high_y & selector))
991
else if (x_scan < x_end)
994
else if (y_scan < y_end)
1004
/* (splice a a-pos b b-pos size)
1005
= (edit a a-pos b b-pos (mask size) size)
1007
Thus, e.g., (extract size pos x) = (splice x pos 0 0 size). */
1011
bignum_splice_bit_field (bignum_type x, unsigned long x_position,
1012
bignum_type y, unsigned long y_position,
1019
/* Ones-complement length. */
775
1022
bignum_length_in_bits (bignum_type bignum)
777
1024
if (BIGNUM_ZERO_P (bignum))
778
return (BIGNUM_ZERO ());
780
1027
bignum_length_type index = ((BIGNUM_LENGTH (bignum)) - 1);
781
bignum_digit_type digit = (BIGNUM_REF (bignum, index));
782
bignum_digit_type delta = 0;
783
bignum_type result = (bignum_allocate (2, 0));
784
(BIGNUM_REF (result, 0)) = index;
785
(BIGNUM_REF (result, 1)) = 0;
786
bignum_destructive_scale_up (result, BIGNUM_DIGIT_LENGTH);
787
ULONG_LENGTH_IN_BITS (digit, delta);
788
bignum_destructive_add (result, ((bignum_digit_type) delta));
789
return (bignum_trim (result));
794
bignum_length_upper_limit (void)
796
bignum_type result = (bignum_allocate (2, 0));
797
(BIGNUM_REF (result, 0)) = 0;
798
(BIGNUM_REF (result, 1)) = BIGNUM_DIGIT_LENGTH;
1029
((ulong_length_in_bits (BIGNUM_REF (bignum, index)))
1030
+ (BIGNUM_DIGIT_LENGTH * index));
1034
/* Two's-complement length. */
1037
bignum_integer_length (bignum_type bignum)
1039
unsigned long length_in_bits = (bignum_length_in_bits (bignum));
1040
if ((BIGNUM_ZERO_P (bignum)) || (BIGNUM_POSITIVE_P (bignum)))
1041
return (length_in_bits);
1042
/* else if (BIGNUM_NEGATIVE_P (bignum)) */
1044
/* We have to test whether it is a negative power of two. If so,
1045
we treat its length as one less than bignum_length_in_bits,
1046
because we are really measuring the length of the finite
1047
sequence of bits before the infinite sequence of zero bits (for
1048
nonnegative integers) or one bits (for negative integers) in the
1049
integer's general two's-complement representation. Thus,
1050
negative powers of two appear to have one fewer bit. */
1051
bignum_digit_type *scan = (BIGNUM_START_PTR (bignum));
1052
bignum_digit_type *end = (scan + (BIGNUM_LENGTH (bignum)) - 1);
1055
return (length_in_bits);
1056
return (length_in_bits - (0 == ((*end) & ((*end) - 1))));
1061
bignum_first_set_bit (bignum_type bignum)
1063
if (BIGNUM_ZERO_P (bignum))
1066
bignum_digit_type *start = (BIGNUM_START_PTR (bignum));
1067
bignum_digit_type *scan = start;
1068
bignum_digit_type *end = (scan + (BIGNUM_LENGTH (bignum)));
1071
if ((*scan) != 0) break;
1074
BIGNUM_ASSERT (scan < end);
1076
((ulong_bit_count (((*scan) ^ ((*scan) - 1)) >> 1))
1077
+ ((scan - start) * BIGNUM_DIGIT_LENGTH));
1081
static inline unsigned long
1082
digits_bit_count (bignum_digit_type **scan_loc, unsigned long count)
1084
unsigned long bit_count = 0;
1085
bignum_digit_type *end = ((*scan_loc) + count);
1086
while ((*scan_loc) < end)
1087
bit_count += (ulong_bit_count (* ((*scan_loc) ++)));
1091
static inline unsigned long
1092
digits_hamming_distance (bignum_digit_type **x_scan_loc,
1093
bignum_digit_type **y_scan_loc,
1094
unsigned long count)
1096
unsigned long hamming_distance = 0;
1097
bignum_digit_type *end = ((*x_scan_loc) + count);
1098
while ((*x_scan_loc) < end)
1100
+= (ulong_bit_count ((* ((*x_scan_loc) ++)) ^ (* ((*y_scan_loc) ++))));
1101
return (hamming_distance);
1104
/* Hamming distance: the easy case. */
1106
static unsigned long
1107
bignum_positive_hamming_distance (bignum_type x, bignum_type y)
1109
BIGNUM_ASSERT (!BIGNUM_ZERO_P (x));
1110
BIGNUM_ASSERT (!BIGNUM_ZERO_P (y));
1111
BIGNUM_ASSERT (BIGNUM_POSITIVE_P (x));
1112
BIGNUM_ASSERT (BIGNUM_POSITIVE_P (y));
1113
if ((BIGNUM_LENGTH (x)) < (BIGNUM_LENGTH (y)))
1115
bignum_type t = x; x = y; y = t;
1118
bignum_digit_type *x_scan = (BIGNUM_START_PTR (x));
1119
bignum_digit_type *y_scan = (BIGNUM_START_PTR (y));
1120
unsigned long hamming_distance
1121
= (digits_hamming_distance
1122
((&x_scan), (&y_scan), (BIGNUM_LENGTH (y))));
1124
+= (digits_bit_count
1125
((&x_scan), ((BIGNUM_LENGTH (x)) - (BIGNUM_LENGTH (y)))));
1126
return (hamming_distance);
1130
/* Hamming distance: the hard case. */
1133
/* Is this actually faster than (hamming-distance (not x) (not y))? */
1135
#define MIN(A,B) (((A) < (B)) ? (A) : (B))
1137
static unsigned long
1138
bignum_negative_hamming_distance (bignum_type x, bignum_type y)
1140
BIGNUM_ASSERT (!BIGNUM_ZERO_P (x));
1141
BIGNUM_ASSERT (!BIGNUM_ZERO_P (y));
1142
BIGNUM_ASSERT (BIGNUM_NEGATIVE_P (x));
1143
BIGNUM_ASSERT (BIGNUM_NEGATIVE_P (y));
1145
bignum_digit_type *x_scan = (BIGNUM_START_PTR (x));
1146
bignum_digit_type *y_scan = (BIGNUM_START_PTR (y));
1147
bignum_digit_type *x_end = (x_scan + (BIGNUM_LENGTH (x)));
1148
bignum_digit_type *y_end = (y_scan + (BIGNUM_LENGTH (y)));
1149
bignum_digit_type x_digit, y_digit;
1150
unsigned long hamming_distance;
1151
/* Find the position of the first nonzero digit of x or y, and
1152
maybe exchange x and y to guarantee that x's is nonzero. */
1155
BIGNUM_ASSERT (x_scan < x_end);
1156
BIGNUM_ASSERT (y_scan < y_end);
1157
x_digit = (*x_scan++);
1158
y_digit = (*y_scan++);
1159
if (x_digit != 0) break;
1162
bignum_digit_type *t;
1163
t = x_scan; x_scan = y_scan; y_scan = t;
1164
t = x_end; x_end = y_end; y_end = t;
1170
/* Convert the first nonzero digit of x and the corresponding digit
1171
(possibly zero) of y to two's-complement. */
1172
x_digit = (-x_digit);
1173
y_digit = (-y_digit);
1175
= (ulong_bit_count ((x_digit ^ y_digit) & BIGNUM_DIGIT_MASK));
1176
/* Skip over zeroes in y. */
1179
bignum_digit_type *y_ptr = y_scan;
1180
bignum_length_type zeroes;
1182
BIGNUM_ASSERT (y_scan < y_end);
1183
y_digit = (*y_scan++);
1184
} while (y_digit == 0);
1185
/* If we any more zeroes, compute the Hamming distance of that
1186
segment as if all corresponding digits of x were ones. */
1187
zeroes = (y_scan - y_ptr - 1);
1188
hamming_distance += (zeroes * BIGNUM_DIGIT_LENGTH);
1189
/* Then subtract the amount by which this overestimated. */
1191
-= (digits_bit_count ((&x_scan), (MIN ((x_end - x_scan), zeroes))));
1192
/* Convert the first nonzero digit of y to two's-complement --
1193
we can subtract 1 because it is nonzero and (semantically,
1194
if not in the type system) unsigned, and hence positive. */
1197
((y_digit - 1) ^ ((x_scan < x_end) ? (*x_scan++) : 0)));
1199
/* Finally, scan over the overlapping parts of x and y and then the
1200
non-overlapping high part of whichever is longer. */
1202
+= (digits_hamming_distance
1203
((&x_scan), (&y_scan), (MIN ((x_end - x_scan), (y_end - y_scan)))));
1205
+= ((x_scan < x_end)
1206
? (digits_bit_count ((&x_scan), (x_end - x_scan)))
1207
: (digits_bit_count ((&y_scan), (y_end - y_scan))));
1208
return (hamming_distance);
1213
static unsigned long
1214
bignum_bit_count_unsigned (bignum_type x)
1216
bignum_digit_type *scan = (BIGNUM_START_PTR (x));
1217
return (digits_bit_count ((&scan), (BIGNUM_LENGTH (x))));
1220
static unsigned long
1221
bignum_negative_hamming_distance (bignum_type x, bignum_type y)
1223
x = (bignum_bitwise_not (x));
1224
y = (bignum_bitwise_not (y));
1225
if (BIGNUM_ZERO_P (x)) return (bignum_bit_count_unsigned (y));
1226
if (BIGNUM_ZERO_P (y)) return (bignum_bit_count_unsigned (x));
1227
return (bignum_positive_hamming_distance (x, y));
1231
bignum_bit_count (bignum_type x) /* a.k.a. Hamming weight, pop count */
1233
if (BIGNUM_ZERO_P (x))
1235
if (BIGNUM_NEGATIVE_P (x))
1236
/* return (bignum_negative_hamming_distance (x, (BIGNUM_ONE (1)))); */
1237
return (bignum_bit_count_unsigned (bignum_bitwise_not (x)));
1239
return (bignum_bit_count_unsigned (x));
1243
bignum_hamming_distance (bignum_type x, bignum_type y)
1247
if (BIGNUM_ZERO_P (x))
1248
return ((BIGNUM_NEGATIVE_P (y)) ? (-1) : (bignum_bit_count_unsigned (y)));
1249
if (BIGNUM_ZERO_P (y))
1250
return ((BIGNUM_NEGATIVE_P (x)) ? (-1) : (bignum_bit_count_unsigned (x)));
1252
((BIGNUM_POSITIVE_P (x))
1253
? ((BIGNUM_POSITIVE_P (y))
1254
? (bignum_positive_hamming_distance (x, y))
1256
: ((BIGNUM_POSITIVE_P (y))
1258
: (bignum_negative_hamming_distance (x, y))));
1264
bignum_nonnegative_one_bits (unsigned long size, unsigned long position)
1267
return (BIGNUM_ZERO ());
1269
unsigned long total = (size + position);
1270
bignum_length_type total_digits = (total / BIGNUM_DIGIT_LENGTH);
1271
bignum_length_type total_bits = (total % BIGNUM_DIGIT_LENGTH);
1272
bignum_length_type zero_digits = (position / BIGNUM_DIGIT_LENGTH);
1273
bignum_length_type zero_bits = (position % BIGNUM_DIGIT_LENGTH);
1274
bignum_length_type one_digits = (size / BIGNUM_DIGIT_LENGTH);
1275
bignum_length_type one_bits = (size % BIGNUM_DIGIT_LENGTH);
1276
bignum_length_type first_nonzero_bits
1277
= (BIGNUM_DIGIT_LENGTH - zero_bits);
1278
bignum_length_type first_one_bits
1279
= ((one_bits < first_nonzero_bits) ? one_bits
1280
: (one_bits - first_nonzero_bits));
1281
bignum_length_type last_one_bits = (one_bits - first_one_bits);
1282
bignum_length_type length = (total_digits + (0 != total_bits));
1283
bignum_type r = (bignum_allocate (length, 0));
1284
bignum_digit_type *r_scan = (BIGNUM_START_PTR (r));
1285
bignum_digit_type *r_zero_end = (r_scan + zero_digits);
1286
bignum_digit_type *r_one_end
1287
= (r_zero_end + (first_one_bits != 0) + one_digits);
1288
BIGNUM_ASSERT ((r_one_end + (last_one_bits != 0)) == (r_scan + length));
1289
while (r_scan < r_zero_end)
1291
if (first_one_bits != 0)
1292
(*r_scan++) = ((BIGNUM_DIGIT_ONES (first_one_bits)) << zero_bits);
1293
while (r_scan < r_one_end)
1294
(*r_scan++) = BIGNUM_DIGIT_MASK;
1295
if (last_one_bits != 0)
1296
(*r_scan++) = (BIGNUM_DIGIT_ONES (last_one_bits));
1304
bignum_nonnegative_one_bits (unsigned long size, unsigned long position)
1308
((bignum_bitwise_not (bignum_shift_left ((BIGNUM_ONE (1)), size))),
1313
bignum_negative_zero_bits (unsigned long n, unsigned long m)
1315
return (bignum_bitwise_not (bignum_nonnegative_one_bits (n, m)));
1319
bignum_shift_right_unsigned (bignum_type n,
1320
unsigned long digits,
1323
bignum_length_type n_length = (BIGNUM_LENGTH (n));
1324
bignum_digit_type *n_start = (BIGNUM_START_PTR (n));
1325
bignum_digit_type *n_scan = (n_start + digits);
1326
bignum_digit_type *n_end = (n_start + n_length);
1327
bignum_length_type r_length
1328
= (n_length - digits
1329
- ((n_start < n_end) && (0 == ((n_end[-1]) >> bits))));
1330
bignum_type r = (bignum_allocate (r_length, 0));
1331
bignum_digit_type *r_scan = (BIGNUM_START_PTR (r));
1333
while (n_scan < n_end)
1334
(*r_scan++) = (*n_scan++);
1337
bignum_digit_type mask = (BIGNUM_DIGIT_ONES (bits));
1338
bignum_digit_type shift = (BIGNUM_DIGIT_LENGTH - bits);
1339
bignum_digit_type extra = ((*n_scan++) >> bits);
1340
while (n_scan < n_end)
1342
bignum_digit_type digit = (*n_scan++);
1343
(*r_scan++) = (((digit & mask) << shift) | extra);
1344
extra = (digit >> bits);
1347
(*r_scan++) = extra;
1348
BIGNUM_ASSERT (r_scan == ((BIGNUM_START_PTR (r)) + r_length));
1354
bignum_shift_right (bignum_type n, unsigned long m)
1356
unsigned long digits = (m / BIGNUM_DIGIT_LENGTH);
1357
unsigned long bits = (m % BIGNUM_DIGIT_LENGTH);
1359
if (digits >= (BIGNUM_LENGTH (n)))
1360
return ((BIGNUM_NEGATIVE_P (n)) ? (BIGNUM_ONE (1)) : (BIGNUM_ZERO ()));
1362
if (BIGNUM_NEGATIVE_P (n))
1365
(bignum_shift_right_unsigned ((bignum_bitwise_not (n)), digits, bits)));
1367
return (bignum_shift_right_unsigned (n, digits, bits));
added
removed
src/microcode/bignum.c
