Branch data Line data Source code
1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : : // Copyright (c) 2009-2022 The Bitcoin Core developers
3 : : // Distributed under the MIT software license, see the accompanying
4 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5 : :
6 : : #include <arith_uint256.h>
7 : :
8 : : #include <uint256.h>
9 : : #include <crypto/common.h>
10 : :
11 : : #include <cassert>
12 : :
13 : : template <unsigned int BITS>
14 : 2970547 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
15 : : {
16 : 2970547 : base_uint<BITS> a(*this);
17 [ + + ]: 26734923 : for (int i = 0; i < WIDTH; i++)
18 : 23764376 : pn[i] = 0;
19 : 2970547 : int k = shift / 32;
20 : 2970547 : shift = shift % 32;
21 [ + + ]: 26734923 : for (int i = 0; i < WIDTH; i++) {
22 [ + + + + ]: 23764376 : if (i + k + 1 < WIDTH && shift != 0)
23 : 3750690 : pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
24 [ + + ]: 23764376 : if (i + k < WIDTH)
25 : 8590287 : pn[i + k] |= (a.pn[i] << shift);
26 : 23764376 : }
27 : 2970547 : return *this;
28 : 2970547 : }
29 : :
30 : : template <unsigned int BITS>
31 : 48394316 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
32 : : {
33 : 48394316 : base_uint<BITS> a(*this);
34 [ + + ]: 435548844 : for (int i = 0; i < WIDTH; i++)
35 : 387154528 : pn[i] = 0;
36 : 48394316 : int k = shift / 32;
37 : 48394316 : shift = shift % 32;
38 [ + + ]: 435548844 : for (int i = 0; i < WIDTH; i++) {
39 [ + + + + ]: 387154528 : if (i - k - 1 >= 0 && shift != 0)
40 : 332794878 : pn[i - k - 1] |= (a.pn[i] << (32 - shift));
41 [ + + ]: 387154528 : if (i - k >= 0)
42 : 381234722 : pn[i - k] |= (a.pn[i] >> shift);
43 : 387154528 : }
44 : 48394316 : return *this;
45 : 48394316 : }
46 : :
47 : : template <unsigned int BITS>
48 : 195094 : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
49 : : {
50 : 195094 : uint64_t carry = 0;
51 [ + + ]: 1755846 : for (int i = 0; i < WIDTH; i++) {
52 : 1560752 : uint64_t n = carry + (uint64_t)b32 * pn[i];
53 : 1560752 : pn[i] = n & 0xffffffff;
54 : 1560752 : carry = n >> 32;
55 : 1560752 : }
56 : 195094 : return *this;
57 : 195094 : }
58 : :
59 : : template <unsigned int BITS>
60 : 199553 : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
61 : : {
62 : 199553 : base_uint<BITS> a;
63 [ + + ]: 1795977 : for (int j = 0; j < WIDTH; j++) {
64 : 1596424 : uint64_t carry = 0;
65 [ + + ]: 8780332 : for (int i = 0; i + j < WIDTH; i++) {
66 : 7183908 : uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
67 : 7183908 : a.pn[i + j] = n & 0xffffffff;
68 : 7183908 : carry = n >> 32;
69 : 7183908 : }
70 : 1596424 : }
71 : 199553 : *this = a;
72 : 199553 : return *this;
73 : 199553 : }
74 : :
75 : : template <unsigned int BITS>
76 : 1152308 : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
77 : : {
78 : 1152308 : base_uint<BITS> div = b; // make a copy, so we can shift.
79 : 1152308 : base_uint<BITS> num = *this; // make a copy, so we can subtract.
80 : 1152308 : *this = 0; // the quotient.
81 : 1152308 : int num_bits = num.bits();
82 : 1152308 : int div_bits = div.bits();
83 [ + + ]: 1152308 : if (div_bits == 0)
84 [ + - + - : 110964 : throw uint_error("Division by zero");
+ - + - ]
85 [ + + ]: 1041344 : if (div_bits > num_bits) // the result is certainly 0.
86 : 161284 : return *this;
87 : 880060 : int shift = num_bits - div_bits;
88 : 880060 : div <<= shift; // shift so that div and num align.
89 [ + + ]: 48400247 : while (shift >= 0) {
90 [ + + ]: 47520187 : if (num >= div) {
91 : 16180219 : num -= div;
92 : 16180219 : pn[shift / 32] |= (1U << (shift & 31)); // set a bit of the result.
93 : 16180219 : }
94 : 47520187 : div >>= 1; // shift back.
95 : 47520187 : shift--;
96 : : }
97 : : // num now contains the remainder of the division.
98 : 880060 : return *this;
99 : 1263272 : }
100 : :
101 : : template <unsigned int BITS>
102 : 491363416 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
103 : : {
104 [ + + - + : 4171366186 : for (int i = WIDTH - 1; i >= 0; i--) {
+ ]
105 [ + + ]: 3680002770 : if (pn[i] < b.pn[i])
106 : 278366191 : return -1;
107 [ + + ]: 3401636579 : if (pn[i] > b.pn[i])
108 : 207980470 : return 1;
109 : 3193656109 : }
110 : 5016755 : return 0;
111 : 491363416 : }
112 : :
113 : : template <unsigned int BITS>
114 : 1731354 : bool base_uint<BITS>::EqualTo(uint64_t b) const
115 : : {
116 [ + + - + : 4915489 : for (int i = WIDTH - 1; i >= 2; i--) {
+ ]
117 [ + + ]: 3184135 : if (pn[i])
118 : 1578066 : return false;
119 : 1606069 : }
120 [ + + ]: 153288 : if (pn[1] != (b >> 32))
121 : 18608 : return false;
122 [ + + ]: 134680 : if (pn[0] != (b & 0xfffffffful))
123 : 13116 : return false;
124 : 121564 : return true;
125 : 1731354 : }
126 : :
127 : : template <unsigned int BITS>
128 : 175033 : double base_uint<BITS>::getdouble() const
129 : : {
130 : 175033 : double ret = 0.0;
131 : 175033 : double fact = 1.0;
132 [ + + ]: 1575297 : for (int i = 0; i < WIDTH; i++) {
133 : 1400264 : ret += fact * pn[i];
134 : 1400264 : fact *= 4294967296.0;
135 : 1400264 : }
136 : 350066 : return ret;
137 : 175033 : }
138 : :
139 : : template <unsigned int BITS>
140 : 3065 : std::string base_uint<BITS>::GetHex() const
141 : : {
142 : 3065 : base_blob<BITS> b;
143 [ + + ]: 27585 : for (int x = 0; x < this->WIDTH; ++x) {
144 : 24520 : WriteLE32(b.begin() + x*4, this->pn[x]);
145 : 24520 : }
146 : 3065 : return b.GetHex();
147 : 3065 : }
148 : :
149 : : template <unsigned int BITS>
150 : 265 : std::string base_uint<BITS>::ToString() const
151 : : {
152 : 265 : return GetHex();
153 : : }
154 : :
155 : : template <unsigned int BITS>
156 : 3386651 : unsigned int base_uint<BITS>::bits() const
157 : : {
158 [ + + - + : 13254778 : for (int pos = WIDTH - 1; pos >= 0; pos--) {
+ ]
159 [ + + ]: 9868127 : if (pn[pos]) {
160 [ + + + + ]: 16317054 : for (int nbits = 31; nbits > 0; nbits--) {
161 [ + + ]: 13407859 : if (pn[pos] & 1U << nbits)
162 : 2853228 : return 32 * pos + nbits + 1;
163 : 10554631 : }
164 : 55967 : return 32 * pos + 1;
165 : : }
166 : 6958932 : }
167 : 477456 : return 0;
168 : 3386651 : }
169 : :
170 : : // Explicit instantiations for base_uint<256>
171 : : template class base_uint<256>;
172 : :
173 : : // This implementation directly uses shifts instead of going
174 : : // through an intermediate MPI representation.
175 : 2213791 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
176 : : {
177 : 2213791 : int nSize = nCompact >> 24;
178 : 2213791 : uint32_t nWord = nCompact & 0x007fffff;
179 [ + + ]: 2213791 : if (nSize <= 3) {
180 : 123304 : nWord >>= 8 * (3 - nSize);
181 : 123304 : *this = nWord;
182 : 123304 : } else {
183 : 2090487 : *this = nWord;
184 : 2090487 : *this <<= 8 * (nSize - 3);
185 : : }
186 [ + + ]: 2213791 : if (pfNegative)
187 [ + + ]: 2017156 : *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
188 [ + + ]: 2213791 : if (pfOverflow)
189 [ + + + + ]: 3941941 : *pfOverflow = nWord != 0 && ((nSize > 34) ||
190 [ + + + + ]: 3245171 : (nWord > 0xff && nSize > 33) ||
191 [ + + ]: 1620364 : (nWord > 0xffff && nSize > 32));
192 : 2213791 : return *this;
193 : 2213791 : }
194 : :
195 : 998760 : uint32_t arith_uint256::GetCompact(bool fNegative) const
196 : : {
197 : 998760 : int nSize = (bits() + 7) / 8;
198 : 998760 : uint32_t nCompact = 0;
199 [ + + ]: 998760 : if (nSize <= 3) {
200 : 124631 : nCompact = GetLow64() << 8 * (3 - nSize);
201 : 124631 : } else {
202 : 874129 : arith_uint256 bn = *this >> 8 * (nSize - 3);
203 : 874129 : nCompact = bn.GetLow64();
204 : 874129 : }
205 : : // The 0x00800000 bit denotes the sign.
206 : : // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
207 [ + + ]: 998760 : if (nCompact & 0x00800000) {
208 : 15930 : nCompact >>= 8;
209 : 15930 : nSize++;
210 : 15930 : }
211 [ + - ]: 998760 : assert((nCompact & ~0x007fffffU) == 0);
212 [ + - ]: 998760 : assert(nSize < 256);
213 : 998760 : nCompact |= nSize << 24;
214 [ + + ]: 998760 : nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
215 : 1997520 : return nCompact;
216 : 998760 : }
217 : :
218 : 265 : uint256 ArithToUint256(const arith_uint256 &a)
219 : : {
220 : 265 : uint256 b;
221 [ + + ]: 2385 : for(int x=0; x<a.WIDTH; ++x)
222 : 2120 : WriteLE32(b.begin() + x*4, a.pn[x]);
223 : 265 : return b;
224 : : }
225 : 2774569 : arith_uint256 UintToArith256(const uint256 &a)
226 : : {
227 : 2774569 : arith_uint256 b;
228 [ + + ]: 24971121 : for(int x=0; x<b.WIDTH; ++x)
229 : 22196552 : b.pn[x] = ReadLE32(a.begin() + x*4);
230 : 2774569 : return b;
231 : : }
|
