OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 // Copyright 2009 The Go Authors. All rights reserved. | 5 // Copyright 2009 The Go Authors. All rights reserved. |
6 // Use of this source code is governed by a BSD-style | 6 // Use of this source code is governed by a BSD-style |
7 // license that can be found in the LICENSE file. | 7 // license that can be found in the LICENSE file. |
8 | 8 |
9 /* | 9 /* |
10 * Copyright (c) 2003-2005 Tom Wu | 10 * Copyright (c) 2003-2005 Tom Wu |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
58 static const int _MIN_INT64 = (-1) << 63; | 58 static const int _MIN_INT64 = (-1) << 63; |
59 static const int _MAX_INT64 = 0x7fffffffffffffff; | 59 static const int _MAX_INT64 = 0x7fffffffffffffff; |
60 | 60 |
61 // Bigint constant values. | 61 // Bigint constant values. |
62 // Note: Not declared as final in order to satisfy optimizer, which expects | 62 // Note: Not declared as final in order to satisfy optimizer, which expects |
63 // constants to be in canonical form (Smi). | 63 // constants to be in canonical form (Smi). |
64 static _Bigint _MINUS_ONE = new _Bigint._fromInt(-1); | 64 static _Bigint _MINUS_ONE = new _Bigint._fromInt(-1); |
65 static _Bigint _ZERO = new _Bigint._fromInt(0); | 65 static _Bigint _ZERO = new _Bigint._fromInt(0); |
66 static _Bigint _ONE = new _Bigint._fromInt(1); | 66 static _Bigint _ONE = new _Bigint._fromInt(1); |
67 | 67 |
| 68 // Result cache for last _divRem call. |
| 69 static Uint32List _lastDividend_digits; |
| 70 static int _lastDividend_used; |
| 71 static Uint32List _lastDivisor_digits; |
| 72 static int _lastDivisor_used; |
| 73 static Uint32List _lastQuoRem_digits; |
| 74 static int _lastQuoRem_used; |
| 75 static int _lastRem_used; |
| 76 static int _lastRem_nsh; |
| 77 |
68 // Internal data structure. | 78 // Internal data structure. |
69 bool get _neg native "Bigint_getNeg"; | 79 bool get _neg native "Bigint_getNeg"; |
70 int get _used native "Bigint_getUsed"; | 80 int get _used native "Bigint_getUsed"; |
71 Uint32List get _digits native "Bigint_getDigits"; | 81 Uint32List get _digits native "Bigint_getDigits"; |
72 | 82 |
73 // Factory returning an instance initialized with the given field values. | 83 // Factory returning an instance initialized with the given field values. |
74 // The 'digits' array is first clamped and 'used' is reduced accordingly. | 84 // The 'digits' array is first clamped and 'used' is reduced accordingly. |
75 // A leading zero digit may be initialized to guarantee that digit pairs can | 85 // A leading zero digit may be initialized to guarantee that digit pairs can |
76 // be processed as 64-bit values on 64-bit platforms. | 86 // be processed as 64-bit values on 64-bit platforms. |
77 factory _Bigint(bool neg, int used, Uint32List digits) | 87 factory _Bigint(bool neg, int used, Uint32List digits) |
(...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
185 return new _Bigint(_neg, r_used, r_digits); | 195 return new _Bigint(_neg, r_used, r_digits); |
186 } | 196 } |
187 | 197 |
188 // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n*_DIGIT_BITS. | 198 // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n*_DIGIT_BITS. |
189 // Return r_used. | 199 // Return r_used. |
190 static int _dlShiftDigits(Uint32List x_digits, int x_used, int n, | 200 static int _dlShiftDigits(Uint32List x_digits, int x_used, int n, |
191 Uint32List r_digits) { | 201 Uint32List r_digits) { |
192 if (x_used == 0) { | 202 if (x_used == 0) { |
193 return 0; | 203 return 0; |
194 } | 204 } |
195 if (n == 0 && r_digits == x_digits) { | 205 if (n == 0 && identical(r_digits, x_digits)) { |
196 return x_used; | 206 return x_used; |
197 } | 207 } |
198 final r_used = x_used + n; | 208 final r_used = x_used + n; |
199 assert(r_digits.length >= r_used + (r_used & 1)); | 209 assert(r_digits.length >= r_used + (r_used & 1)); |
200 var i = x_used; | 210 var i = x_used; |
201 while (--i >= 0) { | 211 while (--i >= 0) { |
202 r_digits[i + n] = x_digits[i]; | 212 r_digits[i + n] = x_digits[i]; |
203 } | 213 } |
204 i = n; | 214 i = n; |
205 while (--i >= 0) { | 215 while (--i >= 0) { |
(...skipping 731 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
937 args[_QD] = _DIGIT_MASK; | 947 args[_QD] = _DIGIT_MASK; |
938 } else { | 948 } else { |
939 args[_QD] = qd; | 949 args[_QD] = qd; |
940 } | 950 } |
941 } | 951 } |
942 return 1; | 952 return 1; |
943 } | 953 } |
944 | 954 |
945 // Return trunc(this / a), a != 0. | 955 // Return trunc(this / a), a != 0. |
946 _Bigint _div(_Bigint a) { | 956 _Bigint _div(_Bigint a) { |
947 return _divRem(a, true); | 957 assert(a._used > 0); |
| 958 if (_used < a._used) { |
| 959 return _ZERO; |
| 960 } |
| 961 _divRem(a); |
| 962 // Return quotient, i.e. |
| 963 // _lastQuoRem_digits[_lastRem_used.._lastQuoRem_used-1] with proper sign. |
| 964 var lastQuo_used = _lastQuoRem_used - _lastRem_used; |
| 965 var quo_digits = _cloneDigits(_lastQuoRem_digits, |
| 966 _lastRem_used, |
| 967 _lastQuoRem_used, |
| 968 lastQuo_used); |
| 969 var quo = new _Bigint(false, lastQuo_used, quo_digits); |
| 970 if ((_neg != a._neg) && (quo._used > 0)) { |
| 971 quo = quo._negate(); |
| 972 } |
| 973 return quo; |
948 } | 974 } |
949 | 975 |
950 // Return this - a * trunc(this / a), a != 0. | 976 // Return this - a * trunc(this / a), a != 0. |
951 _Bigint _rem(_Bigint a) { | 977 _Bigint _rem(_Bigint a) { |
952 return _divRem(a, false); | 978 assert(a._used > 0); |
| 979 if (_used < a._used) { |
| 980 return this; |
| 981 } |
| 982 _divRem(a); |
| 983 // Return remainder, i.e. |
| 984 // denormalized _lastQuoRem_digits[0.._lastRem_used-1] with proper sign. |
| 985 var rem_digits = _cloneDigits(_lastQuoRem_digits, |
| 986 0, |
| 987 _lastRem_used, |
| 988 _lastRem_used); |
| 989 var rem = new _Bigint(false, _lastRem_used, rem_digits); |
| 990 if (_lastRem_nsh > 0) { |
| 991 rem = rem._rShift(_lastRem_nsh); // Denormalize remainder. |
| 992 } |
| 993 if (_neg && (rem._used > 0)) { |
| 994 rem = rem._negate(); |
| 995 } |
| 996 return rem; |
953 } | 997 } |
954 | 998 |
955 // Return trunc(this / a), a != 0, if div == true. | 999 // Cache concatenated positive quotient and normalized positive remainder. |
956 // Return this - a * trunc(this / a), a != 0, if div == false. | 1000 void _divRem(_Bigint a) { |
957 _Bigint _divRem(_Bigint a, bool div) { | 1001 // Check if result is already cached (identical on Bigint is too expensive). |
958 assert(a._used > 0); | 1002 if ((this._used == _lastDividend_used) && |
959 if (_used < a._used) { | 1003 (a._used == _lastDivisor_used) && |
960 return div ? _ZERO : this; | 1004 identical(this._digits, _lastDividend_digits) && |
| 1005 identical(a._digits, _lastDivisor_digits)) { |
| 1006 return; |
961 } | 1007 } |
962 var nsh = _DIGIT_BITS - _nbits(a._digits[a._used - 1]); | 1008 var nsh = _DIGIT_BITS - _nbits(a._digits[a._used - 1]); |
963 // For 64-bit processing, make sure y has an even number of digits. | 1009 // For 64-bit processing, make sure y has an even number of digits. |
964 if (a._used.isOdd) { | 1010 if (a._used.isOdd) { |
965 nsh += _DIGIT_BITS; | 1011 nsh += _DIGIT_BITS; |
966 } | 1012 } |
967 // Concatenated positive quotient and normalized positive remainder. | 1013 // Concatenated positive quotient and normalized positive remainder. |
968 var r_digits; | 1014 var r_digits; |
969 var r_used; | 1015 var r_used; |
970 // Normalized positive divisor. | 1016 // Normalized positive divisor. |
(...skipping 71 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1042 if (yt_qd[_QD] == 0) { | 1088 if (yt_qd[_QD] == 0) { |
1043 --yt_qd[_QD_HI]; | 1089 --yt_qd[_QD_HI]; |
1044 } | 1090 } |
1045 --yt_qd[_QD]; | 1091 --yt_qd[_QD]; |
1046 assert(r_digits[i] <= yt_qd[_QD_HI]); | 1092 assert(r_digits[i] <= yt_qd[_QD_HI]); |
1047 } | 1093 } |
1048 } | 1094 } |
1049 } | 1095 } |
1050 i -= d0; | 1096 i -= d0; |
1051 } | 1097 } |
1052 if (div) { | 1098 // Cache result. |
1053 // Return quotient, i.e. r_digits[y_used..r_used-1] with proper sign. | 1099 _lastDividend_digits = _digits; |
1054 r_digits = _cloneDigits(r_digits, y_used, r_used, r_used - y_used); | 1100 _lastDividend_used = _used; |
1055 var r = new _Bigint(false, r_used - y_used, r_digits); | 1101 _lastDivisor_digits = a._digits; |
1056 if (_neg != a._neg && r._used > 0) { | 1102 _lastDivisor_used = a._used; |
1057 r = r._negate(); | 1103 _lastQuoRem_digits = r_digits; |
1058 } | 1104 _lastQuoRem_used = r_used; |
1059 return r; | 1105 _lastRem_used = y_used; |
1060 } | 1106 _lastRem_nsh = nsh; |
1061 // Return remainder, i.e. denormalized r_digits[0..y_used-1] with | |
1062 // proper sign. | |
1063 r_digits = _cloneDigits(r_digits, 0, y_used, y_used); | |
1064 var r = new _Bigint(false, y_used, r_digits); | |
1065 if (nsh > 0) { | |
1066 r = r._rShift(nsh); // Denormalize remainder. | |
1067 } | |
1068 if (_neg && r._used > 0) { | |
1069 r = r._negate(); | |
1070 } | |
1071 return r; | |
1072 } | 1107 } |
1073 | 1108 |
1074 // Customized version of _rem() minimizing allocations for use in reduction. | 1109 // Customized version of _rem() minimizing allocations for use in reduction. |
1075 // Input: | 1110 // Input: |
1076 // x_digits[0..x_used-1]: positive dividend. | 1111 // x_digits[0..x_used-1]: positive dividend. |
1077 // y_digits[0..y_used-1]: normalized positive divisor. | 1112 // y_digits[0..y_used-1]: normalized positive divisor. |
1078 // ny_digits[0..y_used-1]: negated y_digits. | 1113 // ny_digits[0..y_used-1]: negated y_digits. |
1079 // nsh: normalization shift amount. | 1114 // nsh: normalization shift amount. |
1080 // yt_qd: top y digit(s) and place holder for estimated quotient digit(s). | 1115 // yt_qd: top y digit(s) and place holder for estimated quotient digit(s). |
1081 // t_digits: temp array of 2*y_used digits. | 1116 // t_digits: temp array of 2*y_used digits. |
(...skipping 680 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1762 | 1797 |
1763 int _mul(Uint32List x_digits, int x_used, | 1798 int _mul(Uint32List x_digits, int x_used, |
1764 Uint32List y_digits, int y_used, | 1799 Uint32List y_digits, int y_used, |
1765 Uint32List r_digits) { | 1800 Uint32List r_digits) { |
1766 var r_used = _Bigint._mulDigits(x_digits, x_used, | 1801 var r_used = _Bigint._mulDigits(x_digits, x_used, |
1767 y_digits, y_used, | 1802 y_digits, y_used, |
1768 r_digits); | 1803 r_digits); |
1769 return _reduce(r_digits, r_used); | 1804 return _reduce(r_digits, r_used); |
1770 } | 1805 } |
1771 } | 1806 } |
OLD | NEW |