refactor: modernize the implementation of uint256.* #26345

PastaPastaPasta · 2022-10-19T20:45:00Z

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

w0xlt

Concept ACK

PastaPastaPasta · 2022-10-20T02:23:09Z

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

aureleoules · 2022-10-20T07:55:15Z

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 · 2022-10-20T07:55:53Z

Concept ACK

aureleoules

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:

Fix

diff --git a/src/uint256.h b/src/uint256.h
index d23b2b39a..d5d318baf 100644
--- a/src/uint256.h
+++ b/src/uint256.h
@@ -63,12 +63,11 @@ public:
     constexpr const unsigned char* data() const { return m_data.data(); }
     constexpr unsigned char* data() { return m_data.data(); }
 
-    constexpr unsigned char* begin() { return m_data.begin();}
-    constexpr unsigned char* end() { return m_data.end(); }
+    constexpr unsigned char* begin() { return m_data.data(); }
+    constexpr unsigned char* end() { return m_data.data() + WIDTH; }
 
-    constexpr const unsigned char* begin() const { return m_data.begin(); }
-
-    constexpr const unsigned char* end() const { return m_data.end(); }
+    constexpr const unsigned char* begin() const { return m_data.data(); }
+    constexpr const unsigned char* end() const { return m_data.data() + WIDTH; }
 
     static constexpr unsigned int size() { return WIDTH; }

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

src/uint256.h

PastaPastaPasta · 2022-10-20T17:05:26Z

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)

aureleoules

427d9c9 97b3af2 and 09dc65f look good but should be squashed together yes.

aureleoules

ACK 269481a

PastaPastaPasta · 2022-12-09T17:35:21Z

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

DrahtBot · 2022-12-09T17:35:23Z

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.

sipa

utACK 269481a, one nit

sipa · 2022-12-09T20:01:43Z

src/psbt.h

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


Simpler:

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

hebasto

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:

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

and adjust #includes as suggested by the tool.

hebasto · 2022-12-09T22:04:14Z

src/uint256.h

 public:
    /* construct 0 value by default */
    constexpr base_blob() : m_data() {}

    /* constructor for constants between 1 and 255 */
    constexpr explicit base_blob(uint8_t v) : m_data{v} {}

-    explicit base_blob(const std::vector<unsigned char>& vch);
+    constexpr base_blob(Span<const unsigned char> vch)


Why this constructor is not explicit?

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

src/uint256.h

PastaPastaPasta · 2022-12-09T23:34:51Z

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:
--- a/ci/test/06_script_b.sh
+++ b/ci/test/06_script_b.sh
@@ -57,6 +57,7 @@ if [ "${RUN_TIDY}" = "true" ]; then
           " src/rpc/signmessage.cpp"\
           " src/test/fuzz/txorphan.cpp"\
           " src/test/fuzz/util/"\
+          " src/uint256.cpp"\
           " src/util/bip32.cpp"\
           " src/util/bytevectorhash.cpp"\
           " 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 · 2022-12-10T15:59:24Z

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

Here you are:

diff --git a/ci/test/06_script_b.sh b/ci/test/06_script_b.sh
index 09ce0a1ff1..b1742a5958 100755
--- a/ci/test/06_script_b.sh
+++ b/ci/test/06_script_b.sh
@@ -55,6 +55,7 @@ if [ "${RUN_TIDY}" = "true" ]; then
           " src/rpc/signmessage.cpp"\
           " src/test/fuzz/txorphan.cpp"\
           " src/test/fuzz/util/"\
+          " src/uint256.cpp"\
           " src/util/bip32.cpp"\
           " src/util/bytevectorhash.cpp"\
           " src/util/check.cpp"\
diff --git a/src/uint256.cpp b/src/uint256.cpp
index c31e81003e..7f81c3c448 100644
--- a/src/uint256.cpp
+++ b/src/uint256.cpp
@@ -7,8 +7,6 @@
 
 #include <util/strencodings.h>
 
-#include <string.h>
-
 template <unsigned int BITS>
 std::string base_blob<BITS>::GetHex() const
 {
diff --git a/src/uint256.h b/src/uint256.h
index 240b9eb4c4..782fec8e51 100644
--- a/src/uint256.h
+++ b/src/uint256.h
@@ -9,12 +9,12 @@
 #include <crypto/common.h>
 #include <span.h>
 
+#include <algorithm>
 #include <array>
 #include <cassert>
 #include <cstring>
 #include <stdint.h>
 #include <string>
-#include <vector>
 
 /** Template base class for fixed-sized opaque blobs. */
 template<unsigned int BITS>

And squash your correction commits, please.

PastaPastaPasta · 2022-12-10T17:41:54Z

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

seeking re-ACKs @aureleoules @sipa

hebasto · 2022-12-10T17:46:35Z

May I remind about #26345 (comment)?

PastaPastaPasta · 2022-12-10T17:57:20Z

Sure, why not. Done and fped

hebasto · 2022-12-10T18:39:13Z

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

diff --git a/src/consensus/params.h b/src/consensus/params.h
index 7c35222713..3b5eb1034d 100644
--- a/src/consensus/params.h
+++ b/src/consensus/params.h
@@ -11,6 +11,7 @@
 #include <chrono>
 #include <limits>
 #include <map>
+#include <vector>
 
 namespace Consensus {
 
diff --git a/src/random.h b/src/random.h
index 5fe20c5f76..082ccd4047 100644
--- a/src/random.h
+++ b/src/random.h
@@ -15,6 +15,7 @@
 #include <chrono>
 #include <cstdint>
 #include <limits>
+#include <vector>
 
 /**
  * Overall design of the RNG and entropy sources.

- 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

PastaPastaPasta · 2022-12-10T20:37:10Z

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

hebasto

Approach ACK 935acdc.

hebasto · 2022-12-11T13:53:20Z

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

bitcoin/src/uint256.h

Lines 29 to 30 in 935acdc

    
           /* construct 0 value by default */ 
        
           constexpr base_blob() : m_data() {}

?

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

PastaPastaPasta · 2022-12-12T03:07:14Z

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

bitcoin/src/uint256.h

Lines 29 to 30 in 935acdc

/* construct 0 value by default */

constexpr base_blob() : m_data() {}

?
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.

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

Also, this is what chatGPT says, soo 🤷

aureleoules

reACK 935acdc

john-moffett

ACK 935acdc

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

stickies-v

Approach ACK 935acdc

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.

stickies-v · 2023-02-03T11:00:18Z

src/uint256.h


 /** Template base class for fixed-sized opaque blobs. */
 template<unsigned int BITS>
 class base_blob
 {
 protected:
    static constexpr int WIDTH = BITS / 8;
-    uint8_t m_data[WIDTH];
+    std::array<uint8_t, WIDTH> m_data;
+    static_assert(WIDTH == sizeof(m_data), "Sanity check");


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.

stickies-v · 2023-02-03T11:50:03Z

src/uint256.h

-            if (m_data[i] != 0)
-                return false;
-        return true;
+        return std::all_of(m_data.begin(), m_data.end(), [](uint8_t val) {


Would avoid redefining the value type of m_data

Suggested change

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

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

Or alternatively, could also use typedef uint8_t value_t?

git diff

diff --git a/src/uint256.h b/src/uint256.h index 782fec8e5..0f657a656 100644 --- a/src/uint256.h +++ b/src/uint256.h @@ -21,8 +21,9 @@ template<unsigned int BITS> class base_blob { protected: + typedef uint8_t value_t; static constexpr int WIDTH = BITS / 8; - std::array<uint8_t, WIDTH> m_data; + std::array<value_t, WIDTH> m_data; static_assert(WIDTH == sizeof(m_data), "Sanity check"); public: @@ -30,7 +31,7 @@ public: constexpr base_blob() : m_data() {} /* constructor for constants between 1 and 255 */ - constexpr explicit base_blob(uint8_t v) : m_data{v} {} + constexpr explicit base_blob(value_t v) : m_data{v} {} constexpr explicit base_blob(Span<const unsigned char> vch) { @@ -40,7 +41,7 @@ public: constexpr bool IsNull() const { - return std::all_of(m_data.begin(), m_data.end(), [](uint8_t val) { + return std::all_of(m_data.begin(), m_data.end(), [](value_t val) { return val == 0; }); } @@ -105,7 +106,7 @@ public: class uint256 : public base_blob<256> { public: constexpr uint256() = default; - constexpr explicit uint256(uint8_t v) : base_blob<256>(v) {} + constexpr explicit uint256(value_t v) : base_blob<256>(v) {} constexpr explicit uint256(Span<const unsigned char> vch) : base_blob<256>(vch) {} static const uint256 ZERO; static const uint256 ONE;

stickies-v · 2023-02-03T12:13:35Z

src/uint256.h

    }

-    inline int Compare(const base_blob& other) const { return memcmp(m_data, other.m_data, sizeof(m_data)); }
+    constexpr int Compare(const base_blob& other) const { return std::memcmp(m_data.data(), other.m_data.data(), WIDTH); }


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

Suggested change

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

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

stickies-v · 2023-02-03T12:19:53Z

src/psbt.h

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


nit

Suggested change

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

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

achow101 · 2023-02-06T18:45:16Z

ACK 935acdc

935acdc refactor: modernize the implementation of uint256.* (pasta) Pull request description: - 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 ACKs for top commit: achow101: ACK 935acdc hebasto: Approach ACK 935acdc. aureleoules: reACK 935acdc john-moffett: ACK 935acdc stickies-v: Approach ACK 935acdc Tree-SHA512: 4f1ba54ff2198eea0e505d41e73d552c84c60f6878d5c85a94a8ab57f39afc94ef8d79258e7afd01fa84ec2a99f4404bb877eecd671f65e1ee9273f3129fc650

backport: merge bitcoin#26105, bitcoin#26345 (uint256 modern)

DrahtBot added the Refactoring label Oct 19, 2022

w0xlt reviewed Oct 20, 2022

View reviewed changes

aureleoules reviewed Oct 20, 2022

View reviewed changes

src/uint256.h Outdated Show resolved Hide resolved

PastaPastaPasta requested a review from aureleoules October 20, 2022 17:06

aureleoules reviewed Oct 21, 2022

View reviewed changes

PastaPastaPasta force-pushed the refactor/uint256-modernize branch from 6e82a07 to 269481a Compare October 21, 2022 16:20

PastaPastaPasta requested a review from aureleoules October 25, 2022 22:27

aureleoules approved these changes Oct 25, 2022

View reviewed changes

sipa reviewed Dec 9, 2022

View reviewed changes

hebasto reviewed Dec 9, 2022

View reviewed changes

PastaPastaPasta force-pushed the refactor/uint256-modernize branch from 2dd9f41 to dd7d6d1 Compare December 10, 2022 17:41

PastaPastaPasta force-pushed the refactor/uint256-modernize branch from dd7d6d1 to 9d88a7f Compare December 10, 2022 17:44

PastaPastaPasta force-pushed the refactor/uint256-modernize branch from 9d88a7f to 5ec99b7 Compare December 10, 2022 17:57

PastaPastaPasta force-pushed the refactor/uint256-modernize branch from 5ec99b7 to 935acdc Compare December 10, 2022 20:37

hebasto reviewed Dec 10, 2022

View reviewed changes

aureleoules approved these changes Jan 19, 2023

View reviewed changes

DrahtBot mentioned this pull request Jan 24, 2023

OP_VAULT draft #26857

Closed

DrahtBot mentioned this pull request Feb 2, 2023

test: create random and coins utils, add amount helper, dedupe add_coin #26940

Merged

fanquake requested a review from john-moffett February 2, 2023 10:41

john-moffett approved these changes Feb 2, 2023

View reviewed changes

fanquake requested a review from stickies-v February 2, 2023 16:46

stickies-v reviewed Feb 3, 2023

View reviewed changes

achow101 merged commit 52ddbd5 into bitcoin:master Feb 6, 2023

sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Feb 7, 2023

Merge bitcoin#26345: refactor: modernize the implementation of uint256.*

1da18b0

PastaPastaPasta deleted the refactor/uint256-modernize branch September 27, 2023 14:40

PastaPastaPasta added a commit to dashpay/dash that referenced this pull request Oct 30, 2023

Merge pull request #5587 from PastaPastaPasta/backport-uint256-modern

7440078

backport: merge bitcoin#26105, bitcoin#26345 (uint256 modern)

bitcoin locked and limited conversation to collaborators Sep 26, 2024

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

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

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

refactor: modernize the implementation of uint256.* #26345

refactor: modernize the implementation of uint256.* #26345

Uh oh!

Conversation

PastaPastaPasta commented Oct 19, 2022 • edited by achow101 Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

w0xlt left a comment

Choose a reason for hiding this comment

Uh oh!

PastaPastaPasta commented Oct 20, 2022

Uh oh!

aureleoules commented Oct 20, 2022

Uh oh!

aureleoules commented Oct 20, 2022

Uh oh!

aureleoules left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

PastaPastaPasta commented Oct 20, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

aureleoules left a comment

Choose a reason for hiding this comment

Uh oh!

aureleoules left a comment

Choose a reason for hiding this comment

Uh oh!

PastaPastaPasta commented Dec 9, 2022

Uh oh!

DrahtBot commented Dec 9, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Reviews

Conflicts

Uh oh!

sipa left a comment

Choose a reason for hiding this comment

Uh oh!

sipa Dec 9, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

hebasto left a comment

Choose a reason for hiding this comment

Uh oh!

hebasto Dec 9, 2022

Choose a reason for hiding this comment

Uh oh!

PastaPastaPasta Dec 9, 2022

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

PastaPastaPasta commented Dec 9, 2022

Uh oh!

hebasto commented Dec 10, 2022

Uh oh!

PastaPastaPasta commented Dec 10, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

hebasto commented Dec 10, 2022

Uh oh!

PastaPastaPasta commented Dec 10, 2022

Uh oh!

hebasto commented Dec 10, 2022

Uh oh!

PastaPastaPasta commented Dec 10, 2022

Uh oh!

hebasto left a comment

Choose a reason for hiding this comment

Uh oh!

hebasto commented Dec 11, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

PastaPastaPasta commented Dec 12, 2022

Uh oh!

aureleoules left a comment

Choose a reason for hiding this comment

PastaPastaPasta commented Oct 19, 2022 •

edited by achow101

Loading

PastaPastaPasta commented Oct 20, 2022 •

edited

Loading

DrahtBot commented Dec 9, 2022 •

edited

Loading

sipa Dec 9, 2022 •

edited

Loading

PastaPastaPasta commented Dec 10, 2022 •

edited

Loading

hebasto commented Dec 11, 2022 •

edited

Loading

stickies-v Feb 3, 2023 •

edited

Loading

stickies-v Feb 3, 2023 •

edited

Loading