refactor: modernize the implementation of uint256.*

PastaPastaPasta commented at 8:45 pm on October 19, 2022: contributor

Constructors of uint256 to utilize Span instead of requiring a std::vector
converts m_data into a std::array
Prefers using WIDTH instead of sizeof(m_data)
make all the things constexpr
replace C style functions with c++ equivalents
- memset -> std::fill This may also be replaced by std::memset, but I think that std::fill is more idiomatic of modern c++ and readable.
- memcpy -> std::copy Note: In practice, implementations of std::copy avoid multiple assignments and use bulk copy functions such as std::memmove if the value type is TriviallyCopyable and the iterator types satisfy LegacyContiguousIterator. (https://en.cppreference.com/w/cpp/algorithm/copy) This could also likely be replaced by std::memcpy, but as said above, I believe the using std::copy is the more c++ way to do anything and is almost guaranteed to compile to the same asm
- memcmp -> std::memcmp

DrahtBot added the label Refactoring on Oct 19, 2022

w0xlt commented at 2:22 am on October 20, 2022: contributor

Concept ACK

PastaPastaPasta commented at 2:23 am on October 20, 2022: contributor

Win64 CI failure seems unrelated, would be nice if that could be restarted, or otherwise disregard the failure.

aureleoules commented at 7:55 am on October 20, 2022: member

Win64 CI failure seems unrelated, would be nice if that could be restarted, or otherwise disregard the failure.

I believe you can restart the job yourself on the cirrus-ci’s job page if you have a cirrus-ci account.

aureleoules commented at 7:55 am on October 20, 2022: member

Concept ACK

in src/uint256.h:56 in 427d9c9e3b outdated

64-    friend inline bool operator==(const base_blob& a, const base_blob& b) { return a.Compare(b) == 0; }
65-    friend inline bool operator!=(const base_blob& a, const base_blob& b) { return a.Compare(b) != 0; }
66-    friend inline bool operator<(const base_blob& a, const base_blob& b) { return a.Compare(b) < 0; }
67+    friend constexpr inline bool operator==(const base_blob& a, const base_blob& b) { return a.Compare(b) == 0; }
68+    friend constexpr inline bool operator!=(const base_blob& a, const base_blob& b) { return a.Compare(b) != 0; }
69+    friend constexpr inline bool operator<(const base_blob& a, const base_blob& b) { return a.Compare(b) < 0; }

aureleoules commented at 8:03 am on October 20, 2022:

nit: constexpr is implicitly inline

PastaPastaPasta commented at 4:25 pm on October 20, 2022:

I’ve resolved this

aureleoules commented at 9:17 am on October 20, 2022: member

Win64 CI failure seems unrelated, would be nice if that could be restarted, or otherwise disregard the failure.

The failure is actually related, not sure why, but can be fixed with this patch:

 0diff --git a/src/uint256.h b/src/uint256.h
 1index d23b2b39a..d5d318baf 100644
 2--- a/src/uint256.h
 3+++ b/src/uint256.h
 4@@ -63,12 +63,11 @@ public:
 5     constexpr const unsigned char* data() const { return m_data.data(); }
 6     constexpr unsigned char* data() { return m_data.data(); }
 7 
 8-    constexpr unsigned char* begin() { return m_data.begin();}
 9-    constexpr unsigned char* end() { return m_data.end(); }
10+    constexpr unsigned char* begin() { return m_data.data(); }
11+    constexpr unsigned char* end() { return m_data.data() + WIDTH; }
12 
13-    constexpr const unsigned char* begin() const { return m_data.begin(); }
14-
15-    constexpr const unsigned char* end() const { return m_data.end(); }
16+    constexpr const unsigned char* begin() const { return m_data.data(); }
17+    constexpr const unsigned char* end() const { return m_data.data() + WIDTH; }
18 
19     static constexpr unsigned int size() { return WIDTH; }

See https://cirrus-ci.com/build/5052567852417024 for proof.

PastaPastaPasta commented at 5:05 pm on October 20, 2022: contributor

I’ve pushed 3 additional commits, removing inline where constexpr exists, and then I pushed a commit that adjusts begin() and end() as you suggested, although I think a better solution there may be to simply return auto or to transform the code to be okay with an iterator, but that seems to cause other issues (so I’ve reverted it). Is there any way I can “Win64 native” task on macOS m1 and try to figure that out better?

(Note: I understand all commits will want to be squashed before merge, just trying to figure out those begin() end() methods a bit better atm)

PastaPastaPasta requested review from aureleoules on Oct 20, 2022

aureleoules commented at 9:05 am on October 21, 2022: member

427d9c9e3b6c9fc0abb5399d68bde73270c73be5 97b3af29b1b2d3d845eb9e0d1425129ca77006e9 and 09dc65fbcbb0714abe107098e30487b7432a1c98 look good but should be squashed together yes.

PastaPastaPasta force-pushed on Oct 21, 2022

PastaPastaPasta requested review from aureleoules on Oct 25, 2022

aureleoules approved

aureleoules commented at 11:41 pm on October 25, 2022: member

ACK 269481a84ba1345727f6b12b9318af1f6dde66d2

PastaPastaPasta commented at 5:35 pm on December 9, 2022: contributor

Any movement here? I know review time is precious, but I’d love to see this moved forward 🙈

DrahtBot commented at 5:35 pm on December 9, 2022: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	aureleoules, john-moffett, achow101
Concept ACK	w0xlt
Approach ACK	hebasto, stickies-v
Stale ACK	sipa

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#26940 (test: create random and coins utils, add amount helper, dedupe add_coin by jonatack)
#26857 (OP_VAULT draft by jamesob)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

in src/psbt.h:892 in 269481a84b outdated

888@@ -889,7 +889,7 @@ struct PSBTOutput
889                     } else if (key.size() != 33) {
890                         throw std::ios_base::failure("Output Taproot BIP32 keypath key is not at 33 bytes");
891                     }
892-                    XOnlyPubKey xonly(uint256({key.begin() + 1, key.begin() + 33}));
893+                    XOnlyPubKey xonly(uint256(Span<uint8_t>(key).subspan(/*offset=*/1, /*count=*/32)));

sipa commented at 8:01 pm on December 9, 2022:

Simpler:

0XOnlyPubKey xonly(Span<uint8_t>{key}.last(32));

sipa commented at 8:03 pm on December 9, 2022: member

utACK 269481a84ba1345727f6b12b9318af1f6dde66d2, one nit

in src/uint256.h:34 in 269481a84b outdated

31 
32     /* constructor for constants between 1 and 255 */
33     constexpr explicit base_blob(uint8_t v) : m_data{v} {}
34 
35-    explicit base_blob(const std::vector<unsigned char>& vch);
36+    constexpr base_blob(Span<const unsigned char> vch)

hebasto commented at 10:04 pm on December 9, 2022:

Why this constructor is not explicit?

PastaPastaPasta commented at 11:30 pm on December 9, 2022:

Good point.. Still compiles with it, so I may have missed this one :)

in src/uint256.h:42 in 269481a84b outdated

44     {
45-        for (int i = 0; i < WIDTH; i++)
46-            if (m_data[i] != 0)
47-                return false;
48-        return true;
49+        return std::all_of(m_data.begin(), m_data.end(), [](uint8_t val){

hebasto commented at 10:11 pm on December 9, 2022:

clang-format insists on:

0        return std::all_of(m_data.begin(), m_data.end(), [](uint8_t val) {

in src/uint256.h:66 in 269481a84b outdated

90 
91-    const unsigned char* begin() const
92-    {
93-        return &m_data[0];
94-    }
95+    constexpr unsigned char* begin() { return m_data.data();}

hebasto commented at 10:12 pm on December 9, 2022:

clang-format insists on:

0    constexpr unsigned char* begin() { return m_data.data(); }

in src/uint256.h:26 in 269481a84b outdated

21@@ -21,72 +22,56 @@ class base_blob
22 {
23 protected:
24     static constexpr int WIDTH = BITS / 8;
25-    uint8_t m_data[WIDTH];
26+    std::array<uint8_t, WIDTH> m_data;
27+    static_assert(WIDTH == sizeof(m_data), "Sanity check");

hebasto commented at 10:12 pm on December 9, 2022:

clang-format insists on:

0    static_assert(WIDTH == sizeof(m_data), "Sanity check");

hebasto commented at 10:15 pm on December 9, 2022: member

With such a nice modernization refactoring it seems reasonable to add uint256.cpp to the list of files being processed by the IWYU tool in the CI:

0--- a/ci/test/06_script_b.sh
1+++ b/ci/test/06_script_b.sh
2@@ -57,6 +57,7 @@ if [ "${RUN_TIDY}" = "true" ]; then
3           " src/rpc/signmessage.cpp"\
4           " src/test/fuzz/txorphan.cpp"\
5           " src/test/fuzz/util/"\
6+          " src/uint256.cpp"\
7           " src/util/bip32.cpp"\
8           " src/util/bytevectorhash.cpp"\
9           " src/util/check.cpp"\

and adjust #includes as suggested by the tool.

PastaPastaPasta commented at 11:34 pm on December 9, 2022: contributor

With such a nice modernization refactoring it seems reasonable to add uint256.cpp to the list of files being processed by the IWYU tool in the CI:

0--- a/ci/test/06_script_b.sh
1+++ b/ci/test/06_script_b.sh
2@@ -57,6 +57,7 @@ if [ "${RUN_TIDY}" = "true" ]; then
3           " src/rpc/signmessage.cpp"\
4           " src/test/fuzz/txorphan.cpp"\
5           " src/test/fuzz/util/"\
6+          " src/uint256.cpp"\
7           " src/util/bip32.cpp"\
8           " src/util/bytevectorhash.cpp"\
9           " src/util/check.cpp"\

and adjust #includes as suggested by the tool.

I’ve yet to figure out running this tool / ci locally on my m1 machine.. If you’d like to provide a diff of the includes I can apply it.

hebasto commented at 3:59 pm on December 10, 2022: member

If you’d like to provide a diff of the includes I can apply it.

Here you are:

 0diff --git a/ci/test/06_script_b.sh b/ci/test/06_script_b.sh
 1index 09ce0a1ff1..b1742a5958 100755
 2--- a/ci/test/06_script_b.sh
 3+++ b/ci/test/06_script_b.sh
 4@@ -55,6 +55,7 @@ if [ "${RUN_TIDY}" = "true" ]; then
 5           " src/rpc/signmessage.cpp"\
 6           " src/test/fuzz/txorphan.cpp"\
 7           " src/test/fuzz/util/"\
 8+          " src/uint256.cpp"\
 9           " src/util/bip32.cpp"\
10           " src/util/bytevectorhash.cpp"\
11           " src/util/check.cpp"\
12diff --git a/src/uint256.cpp b/src/uint256.cpp
13index c31e81003e..7f81c3c448 100644
14--- a/src/uint256.cpp
15+++ b/src/uint256.cpp
16@@ -7,8 +7,6 @@
17 
18 #include <util/strencodings.h>
19 
20-#include <string.h>
21-
22 template <unsigned int BITS>
23 std::string base_blob<BITS>::GetHex() const
24 {
25diff --git a/src/uint256.h b/src/uint256.h
26index 240b9eb4c4..782fec8e51 100644
27--- a/src/uint256.h
28+++ b/src/uint256.h
29@@ -9,12 +9,12 @@
30 #include <crypto/common.h>
31 #include <span.h>
32 
33+#include <algorithm>
34 #include <array>
35 #include <cassert>
36 #include <cstring>
37 #include <stdint.h>
38 #include <string>
39-#include <vector>
40 
41 /** Template base class for fixed-sized opaque blobs. */
42 template<unsigned int BITS>

And squash your correction commits, please.

PastaPastaPasta force-pushed on Dec 10, 2022

PastaPastaPasta commented at 5:41 pm on December 10, 2022: contributor

Applied and squashed (and then rebased on master, as there was now a conflict)

seeking re-ACKs @aureleoules @sipa

PastaPastaPasta force-pushed on Dec 10, 2022

hebasto commented at 5:46 pm on December 10, 2022: member

May I remind about #26345 (review)?

PastaPastaPasta force-pushed on Dec 10, 2022

PastaPastaPasta commented at 5:57 pm on December 10, 2022: contributor

Sure, why not. Done and fped

hebasto commented at 6:39 pm on December 10, 2022: member

It looks #include <vector> is required explicitly now:

 0diff --git a/src/consensus/params.h b/src/consensus/params.h
 1index 7c35222713..3b5eb1034d 100644
 2--- a/src/consensus/params.h
 3+++ b/src/consensus/params.h
 4@@ -11,6 +11,7 @@
 5 #include <chrono>
 6 #include <limits>
 7 #include <map>
 8+#include <vector>
 9 
10 namespace Consensus {
11 
12diff --git a/src/random.h b/src/random.h
13index 5fe20c5f76..082ccd4047 100644
14--- a/src/random.h
15+++ b/src/random.h
16@@ -15,6 +15,7 @@
17 #include <chrono>
18 #include <cstdint>
19 #include <limits>
20+#include <vector>
21 
22 /**
23  * Overall design of the RNG and entropy sources.

refactor: modernize the implementation of uint256.*

- Constructors of uint256 to utilize Span instead of requiring a std::vector
- converts m_data into a std::array
- Prefers using `WIDTH` instead of `sizeof(m_data)`
- make all the things constexpr
- replace C style functions with c++ equivalents
    - memset -> std::fill
    - memcpy -> std::copy
        Note: In practice, implementations of std::copy avoid multiple assignments and use bulk copy functions such as std::memmove if the value type is TriviallyCopyable and the iterator types satisfy LegacyContiguousIterator. (https://en.cppreference.com/w/cpp/algorithm/copy)
    - memcmp -> std::memcmp

935acdcc79

PastaPastaPasta force-pushed on Dec 10, 2022

PastaPastaPasta commented at 8:37 pm on December 10, 2022: contributor

Whoops 🙈 that’s what happens when I forget to compile before pushing. Applied change, compiled, and force pushed :)

hebasto commented at 11:10 pm on December 10, 2022: member

Approach ACK 935acdcc79d1dc5ac04a83b92e5919ddbfa29329.

hebasto commented at 1:53 pm on December 11, 2022: member

I’m curios which part of C++ standard guarantees that the following comment is correct: https://github.com/bitcoin/bitcoin/blob/935acdcc79d1dc5ac04a83b92e5919ddbfa29329/src/uint256.h#L29-L30?

Will it result in indeterminate values of uint8_t elements of m_data?

PastaPastaPasta commented at 3:07 am on December 12, 2022: contributor

I’m curios which part of C++ standard guaranties that the following comment is correct:

https://github.com/bitcoin/bitcoin/blob/935acdcc79d1dc5ac04a83b92e5919ddbfa29329/src/uint256.h#L29-L30

? Will it result in indeterminate values of uint8_t elements of m_data?

I’m not sure how exactly it’s guaranteed, but I’m pretty sure it is. I would point towards https://en.cppreference.com/w/cpp/language/zero_initialization

Additionally, you’re able to do this at compile time, and undefined behavior is prohibited at compile time by standard, so that makes me think it’s well defined at runtime as well.

0    constexpr std::array<int, 5> arr{};
1    static_assert(arr[0] == 0, "test");

Also, this is what chatGPT says, soo 🤷

aureleoules approved

aureleoules commented at 11:57 am on January 19, 2023: member

reACK 935acdcc79d1dc5ac04a83b92e5919ddbfa29329

fanquake requested review from john-moffett on Feb 2, 2023

john-moffett approved

john-moffett commented at 3:32 pm on February 2, 2023: contributor

ACK 935acdcc79d1dc5ac04a83b92e5919ddbfa29329

Did a couple quick and dirty sanity-check benchmarks and everything is the same or slightly faster (like Span constructor, as expected).

fanquake requested review from stickies-v on Feb 2, 2023

in src/uint256.h:26 in 935acdcc79

24 {
25 protected:
26     static constexpr int WIDTH = BITS / 8;
27-    uint8_t m_data[WIDTH];
28+    std::array<uint8_t, WIDTH> m_data;
29+    static_assert(WIDTH == sizeof(m_data), "Sanity check");

stickies-v commented at 11:00 am on February 3, 2023:

Given that we’ve just defined m_data to be of size WIDTH the line above, this check seems unnecessary bloat?

“Sanity check” isn’t adding any value as a message imo.

in src/uint256.h:43 in 935acdcc79

47     {
48-        for (int i = 0; i < WIDTH; i++)
49-            if (m_data[i] != 0)
50-                return false;
51-        return true;
52+        return std::all_of(m_data.begin(), m_data.end(), [](uint8_t val) {

stickies-v commented at 11:50 am on February 3, 2023:

Would avoid redefining the value type of m_data

0        return std::all_of(m_data.begin(), m_data.end(), [](auto val) {

stickies-v commented at 12:12 pm on February 3, 2023:

Or alternatively, could also use typedef uint8_t value_t?

 0diff --git a/src/uint256.h b/src/uint256.h
 1index 782fec8e5..0f657a656 100644
 2--- a/src/uint256.h
 3+++ b/src/uint256.h
 4@@ -21,8 +21,9 @@ template<unsigned int BITS>
 5 class base_blob
 6 {
 7 protected:
 8+    typedef uint8_t value_t;
 9     static constexpr int WIDTH = BITS / 8;
10-    std::array<uint8_t, WIDTH> m_data;
11+    std::array<value_t, WIDTH> m_data;
12     static_assert(WIDTH == sizeof(m_data), "Sanity check");
13 
14 public:
15@@ -30,7 +31,7 @@ public:
16     constexpr base_blob() : m_data() {}
17 
18     /* constructor for constants between 1 and 255 */
19-    constexpr explicit base_blob(uint8_t v) : m_data{v} {}
20+    constexpr explicit base_blob(value_t v) : m_data{v} {}
21 
22     constexpr explicit base_blob(Span<const unsigned char> vch)
23     {
24@@ -40,7 +41,7 @@ public:
25 
26     constexpr bool IsNull() const
27     {
28-        return std::all_of(m_data.begin(), m_data.end(), [](uint8_t val) {
29+        return std::all_of(m_data.begin(), m_data.end(), [](value_t val) {
30             return val == 0;
31         });
32     }
33@@ -105,7 +106,7 @@ public:
34 class uint256 : public base_blob<256> {
35 public:
36     constexpr uint256() = default;
37-    constexpr explicit uint256(uint8_t v) : base_blob<256>(v) {}
38+    constexpr explicit uint256(value_t v) : base_blob<256>(v) {}
39     constexpr explicit uint256(Span<const unsigned char> vch) : base_blob<256>(vch) {}
40     static const uint256 ZERO;
41     static const uint256 ONE;

in src/uint256.h:53 in 935acdcc79

60-        memset(m_data, 0, sizeof(m_data));
61+        std::fill(m_data.begin(), m_data.end(), 0);
62     }
63 
64-    inline int Compare(const base_blob& other) const { return memcmp(m_data, other.m_data, sizeof(m_data)); }
65+    constexpr int Compare(const base_blob& other) const { return std::memcmp(m_data.data(), other.m_data.data(), WIDTH); }

stickies-v commented at 12:13 pm on February 3, 2023:

nit: we’ve already defined member function data() to return m_data.data() (+ in a bunch more lines further down and in uint256.cpp)

0    constexpr int Compare(const base_blob& other) const { return std::memcmp(data(), other.data(), WIDTH); }

in src/psbt.h:892 in 935acdcc79

888@@ -889,7 +889,7 @@ struct PSBTOutput
889                     } else if (key.size() != 33) {
890                         throw std::ios_base::failure("Output Taproot BIP32 keypath key is not at 33 bytes");
891                     }
892-                    XOnlyPubKey xonly(uint256({key.begin() + 1, key.begin() + 33}));
893+                    XOnlyPubKey xonly(uint256(Span<uint8_t>(key).last(32)));

stickies-v commented at 12:19 pm on February 3, 2023:

nit

0                    XOnlyPubKey xonly(uint256{Span<uint8_t>(key).last(32)});

stickies-v commented at 12:22 pm on February 3, 2023: contributor

Approach ACK 935acdcc7

Not a very high confidence review, I’m not very familiar with the nuances of switching from C to C++ functions/objects - may be missing unintentional side effects.

achow101 commented at 6:45 pm on February 6, 2023: member

ACK 935acdcc79d1dc5ac04a83b92e5919ddbfa29329

achow101 merged this on Feb 6, 2023

achow101 closed this on Feb 6, 2023

sidhujag referenced this in commit 1da18b0d8b on Feb 7, 2023

PastaPastaPasta deleted the branch on Sep 27, 2023

PastaPastaPasta referenced this in commit 154a2d180f on Sep 28, 2023

PastaPastaPasta referenced this in commit 3ca95f3f35 on Sep 28, 2023

PastaPastaPasta referenced this in commit 3e82b7040f on Sep 28, 2023

PastaPastaPasta referenced this in commit 5364fcfb61 on Oct 5, 2023

PastaPastaPasta referenced this in commit 9f7eeca24c on Oct 28, 2023

PastaPastaPasta referenced this in commit 5ad6088c93 on Oct 30, 2023

PastaPastaPasta referenced this in commit 7440078f5d on Oct 30, 2023

bitcoin locked this on Sep 26, 2024

refactor: modernize the implementation of uint256.* #26345

Reviews

Conflicts