1// Copyright (c) 2009-2010 Satoshi Nakamoto
2// Copyright (c) 2009-present 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#ifndef BITCOIN_ARITH_UINT256_H
7#define BITCOIN_ARITH_UINT256_H
8
9#include <compare>
10#include <cstdint>
11#include <cstring>
12#include <limits>
13#include <stdexcept>
14#include <string>
15
16class uint256;
17
18class uint_error : public std::runtime_error {
19public:
20    explicit uint_error(const std::string& str) : std::runtime_error(str) {}
21};
22
23/** Template base class for unsigned big integers. */
24template <unsigned int BITS>
25class base_uint
26{
27protected:
28    static_assert(BITS / 32 > 0 && BITS % 32 == 0, "Template parameter BITS must be a positive multiple of 32.");
29    static constexpr int WIDTH = BITS / 32;
30    /** Big integer represented with 32-bit digits, least-significant first. */
31    uint32_t pn[WIDTH];
32
33public:
34    constexpr base_uint()
35    {
36        for (int i = 0; i < WIDTH; i++)
37            pn[i] = 0;
38    }
39
40    base_uint(const base_uint& b) = default;
41    base_uint& operator=(const base_uint& b) = default;
42
43    constexpr base_uint(uint64_t b)
44    {
45        pn[0] = (unsigned int)b;
46        pn[1] = (unsigned int)(b >> 32);
47        for (int i = 2; i < WIDTH; i++)
48            pn[i] = 0;
49    }
50
51    base_uint operator~() const
52    {
53        base_uint ret;
54        for (int i = 0; i < WIDTH; i++)
55            ret.pn[i] = ~pn[i];
56        return ret;
57    }
58
59    base_uint operator-() const
60    {
61        base_uint ret;
62        for (int i = 0; i < WIDTH; i++)
63            ret.pn[i] = ~pn[i];
64        ++ret;
65        return ret;
66    }
67
68    double getdouble() const;
69
70    base_uint& operator=(uint64_t b)
71    {
72        pn[0] = (unsigned int)b;
73        pn[1] = (unsigned int)(b >> 32);
74        for (int i = 2; i < WIDTH; i++)
75            pn[i] = 0;
76        return *this;
77    }
78
79    base_uint& operator^=(const base_uint& b)
80    {
81        for (int i = 0; i < WIDTH; i++)
82            pn[i] ^= b.pn[i];
83        return *this;
84    }
85
86    base_uint& operator&=(const base_uint& b)
87    {
88        for (int i = 0; i < WIDTH; i++)
89            pn[i] &= b.pn[i];
90        return *this;
91    }
92
93    base_uint& operator|=(const base_uint& b)
94    {
95        for (int i = 0; i < WIDTH; i++)
96            pn[i] |= b.pn[i];
97        return *this;
98    }
99
100    base_uint& operator^=(uint64_t b)
101    {
102        pn[0] ^= (unsigned int)b;
103        pn[1] ^= (unsigned int)(b >> 32);
104        return *this;
105    }
106
107    base_uint& operator|=(uint64_t b)
108    {
109        pn[0] |= (unsigned int)b;
110        pn[1] |= (unsigned int)(b >> 32);
111        return *this;
112    }
113
114    base_uint& operator<<=(unsigned int shift);
115    base_uint& operator>>=(unsigned int shift);
116
117    base_uint& operator+=(const base_uint& b)
118    {
119        uint64_t carry = 0;
120        for (int i = 0; i < WIDTH; i++)
121        {
122            uint64_t n = carry + pn[i] + b.pn[i];
123            pn[i] = n & 0xffffffff;
124            carry = n >> 32;
125        }
126        return *this;
127    }
128
129    base_uint& operator-=(const base_uint& b)
130    {
131        *this += -b;
132        return *this;
133    }
134
135    base_uint& operator+=(uint64_t b64)
136    {
137        base_uint b;
138        b = b64;
139        *this += b;
140        return *this;
141    }
142
143    base_uint& operator-=(uint64_t b64)
144    {
145        base_uint b;
146        b = b64;
147        *this += -b;
148        return *this;
149    }
150
151    base_uint& operator*=(uint32_t b32);
152    base_uint& operator*=(const base_uint& b);
153    base_uint& operator/=(const base_uint& b);
154
155    base_uint& operator++()
156    {
157        // prefix operator
158        int i = 0;
159        while (i < WIDTH && ++pn[i] == 0)
160            i++;
161        return *this;
162    }
163
164    base_uint operator++(int)
165    {
166        // postfix operator
167        const base_uint ret = *this;
168        ++(*this);
169        return ret;
170    }
171
172    base_uint& operator--()
173    {
174        // prefix operator
175        int i = 0;
176        while (i < WIDTH && --pn[i] == std::numeric_limits<uint32_t>::max())
177            i++;
178        return *this;
179    }
180
181    base_uint operator--(int)
182    {
183        // postfix operator
184        const base_uint ret = *this;
185        --(*this);
186        return ret;
187    }
188
189    /** Numeric ordering (unlike \ref base_blob::Compare) */
190    int CompareTo(const base_uint& b) const;
191    bool EqualTo(uint64_t b) const;
192
193    friend inline base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; }
194    friend inline base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; }
195    friend inline base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; }
196    friend inline base_uint operator/(const base_uint& a, const base_uint& b) { return base_uint(a) /= b; }
197    friend inline base_uint operator|(const base_uint& a, const base_uint& b) { return base_uint(a) |= b; }
198    friend inline base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; }
199    friend inline base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; }
200    friend inline base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; }
201    friend inline base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
202    friend inline base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
203    friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
204    friend inline std::strong_ordering operator<=>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <=> 0; }
205    friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
206
207    /** Hex encoding of the number (with the most significant digits first). */
208    std::string GetHex() const;
209    std::string ToString() const;
210
211    unsigned int size() const
212    {
213        return sizeof(pn);
214    }
215
216    /**
217     * Returns the position of the highest bit set plus one, or zero if the
218     * value is zero.
219     */
220    unsigned int bits() const;
221
222    uint64_t GetLow64() const
223    {
224        static_assert(WIDTH >= 2, "Assertion WIDTH >= 2 failed (WIDTH = BITS / 32). BITS is a template parameter.");
225        return pn[0] | (uint64_t)pn[1] << 32;
226    }
227};
228
229/** 256-bit unsigned big integer. */
230class arith_uint256 : public base_uint<256>
231{
232public:
233    constexpr arith_uint256() = default;
234    constexpr arith_uint256(const base_uint& b) : base_uint(b) {}
235    constexpr arith_uint256(uint64_t b) : base_uint(b) {}
236
237    /**
238     * The "compact" format is a representation of a whole
239     * number N using an unsigned 32bit number similar to a
240     * floating point format.
241     * The most significant 8 bits are the unsigned exponent of base 256.
242     * This exponent can be thought of as "number of bytes of N".
243     * The lower 23 bits are the mantissa.
244     * Bit number 24 (0x800000) represents the sign of N.
245     * N = (-1^sign) * mantissa * 256^(exponent-3)
246     *
247     * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn().
248     * MPI uses the most significant bit of the first byte as sign.
249     * Thus 0x1234560000 is compact (0x05123456)
250     * and  0xc0de000000 is compact (0x0600c0de)