arith_uint256.cpp raw
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2022 The Limenka 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 base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
15 {
16 base_uint<BITS> a(*this);
17 for (int i = 0; i < WIDTH; i++)
18 pn[i] = 0;
19 int k = shift / 32;
20 shift = shift % 32;
21 for (int i = 0; i < WIDTH; i++) {
22 if (i + k + 1 < WIDTH && shift != 0)
23 pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
24 if (i + k < WIDTH)
25 pn[i + k] |= (a.pn[i] << shift);
26 }
27 return *this;
28 }
29
30 template <unsigned int BITS>
31 base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
32 {
33 base_uint<BITS> a(*this);
34 for (int i = 0; i < WIDTH; i++)
35 pn[i] = 0;
36 int k = shift / 32;
37 shift = shift % 32;
38 for (int i = 0; i < WIDTH; i++) {
39 if (i - k - 1 >= 0 && shift != 0)
40 pn[i - k - 1] |= (a.pn[i] << (32 - shift));
41 if (i - k >= 0)
42 pn[i - k] |= (a.pn[i] >> shift);
43 }
44 return *this;
45 }
46
47 template <unsigned int BITS>
48 base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
49 {
50 uint64_t carry = 0;
51 for (int i = 0; i < WIDTH; i++) {
52 uint64_t n = carry + (uint64_t)b32 * pn[i];
53 pn[i] = n & 0xffffffff;
54 carry = n >> 32;
55 }
56 return *this;
57 }
58
59 template <unsigned int BITS>
60 base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
61 {
62 base_uint<BITS> a;
63 for (int j = 0; j < WIDTH; j++) {
64 uint64_t carry = 0;
65 for (int i = 0; i + j < WIDTH; i++) {
66 uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
67 a.pn[i + j] = n & 0xffffffff;
68 carry = n >> 32;
69 }
70 }
71 *this = a;
72 return *this;
73 }
74
75 template <unsigned int BITS>
76 base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
77 {
78 base_uint<BITS> div = b; // make a copy, so we can shift.
79 base_uint<BITS> num = *this; // make a copy, so we can subtract.
80 *this = 0; // the quotient.
81 int num_bits = num.bits();
82 int div_bits = div.bits();
83 if (div_bits == 0)
84 throw uint_error("Division by zero");
85 if (div_bits > num_bits) // the result is certainly 0.
86 return *this;
87 int shift = num_bits - div_bits;
88 div <<= shift; // shift so that div and num align.
89 while (shift >= 0) {
90 if (num >= div) {
91 num -= div;
92 pn[shift / 32] |= (1U << (shift & 31)); // set a bit of the result.
93 }
94 div >>= 1; // shift back.
95 shift--;
96 }
97 // num now contains the remainder of the division.
98 return *this;
99 }
100
101 template <unsigned int BITS>
102 int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
103 {
104 for (int i = WIDTH - 1; i >= 0; i--) {
105 if (pn[i] < b.pn[i])
106 return -1;
107 if (pn[i] > b.pn[i])
108 return 1;
109 }
110 return 0;
111 }
112
113 template <unsigned int BITS>
114 bool base_uint<BITS>::EqualTo(uint64_t b) const
115 {
116 for (int i = WIDTH - 1; i >= 2; i--) {
117 if (pn[i])
118 return false;
119 }
120 if (pn[1] != (b >> 32))
121 return false;
122 if (pn[0] != (b & 0xfffffffful))
123 return false;
124 return true;
125 }
126
127 template <unsigned int BITS>
128 double base_uint<BITS>::getdouble() const
129 {
130 double ret = 0.0;
131 double fact = 1.0;
132 for (int i = 0; i < WIDTH; i++) {
133 ret += fact * pn[i];
134 fact *= 4294967296.0;
135 }
136 return ret;
137 }
138
139 template <unsigned int BITS>
140 std::string base_uint<BITS>::GetHex() const
141 {
142 base_blob<BITS> b;
143 for (int x = 0; x < this->WIDTH; ++x) {
144 WriteLE32(b.begin() + x*4, this->pn[x]);
145 }
146 return b.GetHex();
147 }
148
149 template <unsigned int BITS>
150 std::string base_uint<BITS>::ToString() const
151 {
152 return GetHex();
153 }
154
155 template <unsigned int BITS>
156 unsigned int base_uint<BITS>::bits() const
157 {
158 for (int pos = WIDTH - 1; pos >= 0; pos--) {
159 if (pn[pos]) {
160 for (int nbits = 31; nbits > 0; nbits--) {
161 if (pn[pos] & 1U << nbits)
162 return 32 * pos + nbits + 1;
163 }
164 return 32 * pos + 1;
165 }
166 }
167 return 0;
168 }
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 arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
176 {
177 int nSize = nCompact >> 24;
178 uint32_t nWord = nCompact & 0x007fffff;
179 if (nSize <= 3) {
180 nWord >>= 8 * (3 - nSize);
181 *this = nWord;
182 } else {
183 *this = nWord;
184 *this <<= 8 * (nSize - 3);
185 }
186 if (pfNegative)
187 *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
188 if (pfOverflow)
189 *pfOverflow = nWord != 0 && ((nSize > 34) ||
190 (nWord > 0xff && nSize > 33) ||
191 (nWord > 0xffff && nSize > 32));
192 return *this;
193 }
194
195 uint32_t arith_uint256::GetCompact(bool fNegative) const
196 {
197 int nSize = (bits() + 7) / 8;
198 uint32_t nCompact = 0;
199 if (nSize <= 3) {
200 nCompact = GetLow64() << 8 * (3 - nSize);
201 } else {
202 arith_uint256 bn = *this >> 8 * (nSize - 3);
203 nCompact = bn.GetLow64();
204 }
205 // The 0x00800000 bit denotes the sign.
206 // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
207 if (nCompact & 0x00800000) {
208 nCompact >>= 8;
209 nSize++;
210 }
211 assert((nCompact & ~0x007fffffU) == 0);
212 assert(nSize < 256);
213 nCompact |= nSize << 24;
214 nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
215 return nCompact;
216 }
217
218 uint256 ArithToUint256(const arith_uint256 &a)
219 {
220 uint256 b;
221 for(int x=0; x<a.WIDTH; ++x)
222 WriteLE32(b.begin() + x*4, a.pn[x]);
223 return b;
224 }
225 arith_uint256 UintToArith256(const uint256 &a)
226 {
227 arith_uint256 b;
228 for(int x=0; x<b.WIDTH; ++x)
229 b.pn[x] = ReadLE32(a.begin() + x*4);
230 return b;
231 }
232
233 // Explicit instantiations for base_uint<6144> (used in test/fuzz/muhash.cpp).
234 template base_uint<6144>& base_uint<6144>::operator*=(const base_uint<6144>& b);
235 template base_uint<6144>& base_uint<6144>::operator/=(const base_uint<6144>& b);
236