Skip to content

Avoid overflowing shift by special casing inverse of 1 #81

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 1 commit into from
Apr 12, 2024
Merged

Avoid overflowing shift by special casing inverse of 1 #81

merged 1 commit into from
Apr 12, 2024

Conversation

sipa
Copy link
Collaborator

@sipa sipa commented Apr 3, 2024

When x=1, then rlen = BITS+1 and newrlen = 1, and thus in the first loop iteration q = BITS, leading to a shift by BITS bits, which may overflow the integer type.

Avoid this situation by special casing x=1. The inverse of 1 is always 1 anyway.

@sipa sipa mentioned this pull request Apr 3, 2024
Closed
1 task
@sipa sipa force-pushed the 202404_special_inv_one branch from 89c7e0a to 52f5d5d Compare April 10, 2024 07:51
@sipa sipa force-pushed the 202404_special_inv_one branch from 52f5d5d to 653d8b2 Compare April 11, 2024 09:47
@theuni
Copy link
Contributor

theuni commented Apr 11, 2024

I can't say I fully understand how we arrive here, but given the fuzzer find and sipa's dumbing down of the problem:

Avoid this situation by special casing x=1. The inverse of 1 is always 1 anyway.

Trivial ACK 653d8b2. This does that :)

@theuni
Copy link
Contributor

theuni commented Apr 11, 2024

Looking again, is there any way to return x based on template params alone to potentially eliminate these runtime checks?

@sipa
Copy link
Collaborator Author

sipa commented Apr 11, 2024

@theuni x is only known at runtime in the relevant call sites. If it were statically known, there is no need to call the function in the first place.

@fanquake fanquake mentioned this pull request Apr 11, 2024
Merged
@sipa sipa merged commit 3472e2f into master Apr 12, 2024
fanquake added a commit to fanquake/bitcoin that referenced this pull request Apr 12, 2024
@fanquake
Squashed 'src/minisketch/' changes from a571ba20f9..3472e2f5ec
1eea10a 
3472e2f5ec Merge bitcoin-core/minisketch#81: Avoid overflowing shift by special casing inverse of 1
653d8b2e26 Avoid overflowing shift by special casing inverse of 1
33b7c200b9 Merge bitcoin-core/minisketch#80: Add c++20 version of CountBits
4a48f31a37 Merge bitcoin-core/minisketch#83: ci: Fix "s390x (big-endian)" task
82b6488acb Add c++20 version of CountBits
0498084d31 ci: Fix "s390x (big-endian)" task
71709dca9e Merge bitcoin-core/minisketch#82: ci: Fix `x86_64-w64-mingw32` task
9e6127fa98 Merge bitcoin-core/minisketch#74: Avoid >> above type width in BitWriter
ed420bc170 ci: Fix `x86_64-w64-mingw32` task
fe1040f227 Drop -Wno-shift-count-overflow compile flag
154bcd43bd Avoid >> above type width in BitWriter
67b87acdb6 Merge bitcoin-core/minisketch#78: ci: Update macOS image for CI
7de7250416 ci: Update macOS image for CI
83d812ea9f Merge bitcoin-core/minisketch#73: ci: Use correct variable to designate C++ compiler
e051a7d690 ci: Install wine32 package for Windows tests
2d2c695d78 build: Drop unused `CC` variable
1810fcbd11 ci: Use correct variable to designate C++ compiler
022b959049 Merge bitcoin-core/minisketch#77: Add missing include
08443c4892 Add missing include

git-subtree-dir: src/minisketch
git-subtree-split: 3472e2f5ec75ace39ce9243af6b3fee233a67492
fanquake added a commit to bitcoin/bitcoin that referenced this pull request Apr 15, 2024
@fanquake
Merge #29823: minisketch: update subtree to 3472e2f5ec75ace39ce9243af…
d29fc3a 
…6b3fee233a67492

4722b7c build: remove minisketch clz check (fanquake)
1eea10a Squashed 'src/minisketch/' changes from a571ba20f9..3472e2f5ec (fanquake)

Pull request description:

  bitcoin-core/minisketch#81 will fix #29799.
  Minor build cleanups after bitcoin-core/minisketch#80.

ACKs for top commit:
  dergoegge:
    utACK 4722b7c
  hebasto:
    ACK 4722b7c, I have verified the subtree update and reviewed the build system changes. Both look OK.

Tree-SHA512: eabd82e5a13cc4f32155319df97368f2e8c93320a4265b6c372efcb1ea4e756f6693df7c02498c8ea989ccd376a20277fa110c66d0754cb9bca5e54d18e0a965
janus pushed a commit to BitgesellOfficial/bitgesell that referenced this pull request Jun 6, 2024
@fanquake @janus
Squashed 'src/minisketch/' changes from a571ba20f9..3472e2f5ec
b47db96 
3472e2f5ec Merge bitcoin-core/minisketch#81: Avoid overflowing shift by special casing inverse of 1
653d8b2e26 Avoid overflowing shift by special casing inverse of 1
33b7c200b9 Merge bitcoin-core/minisketch#80: Add c++20 version of CountBits
4a48f31a37 Merge bitcoin-core/minisketch#83: ci: Fix "s390x (big-endian)" task
82b6488acb Add c++20 version of CountBits
0498084d31 ci: Fix "s390x (big-endian)" task
71709dca9e Merge bitcoin-core/minisketch#82: ci: Fix `x86_64-w64-mingw32` task
9e6127fa98 Merge bitcoin-core/minisketch#74: Avoid >> above type width in BitWriter
ed420bc170 ci: Fix `x86_64-w64-mingw32` task
fe1040f227 Drop -Wno-shift-count-overflow compile flag
154bcd43bd Avoid >> above type width in BitWriter
67b87acdb6 Merge bitcoin-core/minisketch#78: ci: Update macOS image for CI
7de7250416 ci: Update macOS image for CI
83d812ea9f Merge bitcoin-core/minisketch#73: ci: Use correct variable to designate C++ compiler
e051a7d690 ci: Install wine32 package for Windows tests
2d2c695d78 build: Drop unused `CC` variable
1810fcbd11 ci: Use correct variable to designate C++ compiler
022b959049 Merge bitcoin-core/minisketch#77: Add missing include
08443c4892 Add missing include

git-subtree-dir: src/minisketch
git-subtree-split: 3472e2f5ec75ace39ce9243af6b3fee233a67492
vmta added a commit to umkoin/umkoin that referenced this pull request Oct 6, 2024
@vmta
Squashed 'src/minisketch/' changes from a223557ce..eb37a9b8e
21eb7a8 
eb37a9b8e Merge bitcoin-core/minisketch#87: Avoid copy in self-assign
fe6557642 Merge bitcoin-core/minisketch#88: build: Add `-Wundef`
8ea298bfa Avoid copy in self-assign
978a3d886 build: Add `-Wundef`
338704417 Merge bitcoin-core/minisketch#86: doc: fix typo in sketch_impl.h
15c2d13b6 doc: fix typo in sketch_impl.h
7be08b8a4 Merge bitcoin-core/minisketch#85: Fixes for integer precision loss
00fb4a4d8 Avoid or make integer precision conversion explicit
9d62a4d27 Avoid the need to cast/convert to size_t for vector operations
19e06cc7a Prevent overflows from large capacity/max_elements
3472e2f5e Merge bitcoin-core/minisketch#81: Avoid overflowing shift by special casing inverse of 1
653d8b2e2 Avoid overflowing shift by special casing inverse of 1
33b7c200b Merge bitcoin-core/minisketch#80: Add c++20 version of CountBits
4a48f31a3 Merge bitcoin-core/minisketch#83: ci: Fix "s390x (big-endian)" task
82b6488ac Add c++20 version of CountBits
0498084d3 ci: Fix "s390x (big-endian)" task
71709dca9 Merge bitcoin-core/minisketch#82: ci: Fix `x86_64-w64-mingw32` task
9e6127fa9 Merge bitcoin-core/minisketch#74: Avoid >> above type width in BitWriter
ed420bc17 ci: Fix `x86_64-w64-mingw32` task
fe1040f22 Drop -Wno-shift-count-overflow compile flag
154bcd43b Avoid >> above type width in BitWriter
67b87acdb Merge bitcoin-core/minisketch#78: ci: Update macOS image for CI
7de725041 ci: Update macOS image for CI
83d812ea9 Merge bitcoin-core/minisketch#73: ci: Use correct variable to designate C++ compiler
e051a7d69 ci: Install wine32 package for Windows tests
2d2c695d7 build: Drop unused `CC` variable
1810fcbd1 ci: Use correct variable to designate C++ compiler
022b95904 Merge bitcoin-core/minisketch#77: Add missing include
08443c489 Add missing include
a571ba20f Merge bitcoin-core/minisketch#68: Add missed `#include <string>`
b9a7f7e2b Merge bitcoin-core/minisketch#69: refactor: Drop unused `total` local variables
8a5af94ed Merge bitcoin-core/minisketch#70: build: Remove `-Qunused-arguments` workaround for clang + ccache
c36f1f03a Merge bitcoin-core/minisketch#72: Fix MSVC implementation of `CountBits()` function
0078bedda Ignore `HAVE_CLZ` macro when building with MSVC
1c772918c Fix MSVC implementation of `CountBits()` function
98f87c55f build: Remove `-Qunused-arguments` workaround for clang + ccache
11a1e25c8 refactor: Drop unused `total` local variables
ed6c8fcfd Add missed `#include <string>`
47f0a2d26 Merge bitcoin-core/minisketch#66: msvc: remove direct Bitcoin Core `compat.h` include
64f17584c msvc: remove Core compat.h include

git-subtree-dir: src/minisketch
git-subtree-split: eb37a9b8e79f9e49d73b96a49bf97a96d9eb676c
kwvg added a commit to kwvg/dash that referenced this pull request Oct 29, 2024
@kwvg
Squashed 'src/minisketch/' changes from a571ba20f9..3472e2f5ec
9540ecb 
3472e2f5ec Merge bitcoin-core/minisketch#81: Avoid overflowing shift by special casing inverse of 1
653d8b2e26 Avoid overflowing shift by special casing inverse of 1
33b7c200b9 Merge bitcoin-core/minisketch#80: Add c++20 version of CountBits
4a48f31a37 Merge bitcoin-core/minisketch#83: ci: Fix "s390x (big-endian)" task
82b6488acb Add c++20 version of CountBits
0498084d31 ci: Fix "s390x (big-endian)" task
71709dca9e Merge bitcoin-core/minisketch#82: ci: Fix `x86_64-w64-mingw32` task
9e6127fa98 Merge bitcoin-core/minisketch#74: Avoid >> above type width in BitWriter
ed420bc170 ci: Fix `x86_64-w64-mingw32` task
fe1040f227 Drop -Wno-shift-count-overflow compile flag
154bcd43bd Avoid >> above type width in BitWriter
67b87acdb6 Merge bitcoin-core/minisketch#78: ci: Update macOS image for CI
7de7250416 ci: Update macOS image for CI
83d812ea9f Merge bitcoin-core/minisketch#73: ci: Use correct variable to designate C++ compiler
e051a7d690 ci: Install wine32 package for Windows tests
2d2c695d78 build: Drop unused `CC` variable
1810fcbd11 ci: Use correct variable to designate C++ compiler
022b959049 Merge bitcoin-core/minisketch#77: Add missing include
08443c4892 Add missing include

git-subtree-dir: src/minisketch
git-subtree-split: 3472e2f5ec75ace39ce9243af6b3fee233a67492
@kwvg kwvg mentioned this pull request Oct 29, 2024
Merged
5 tasks
PastaPastaPasta added a commit to dashpay/dash that referenced this pull request Oct 29, 2024
@PastaPastaPasta
Merge #6372: backport: merge bitcoin#29823, bitcoin#30270 (update 'sr…
02ec0fd 
…c/minisketch' to bitcoin-core/minisketch@eb37a9b8)

5e65bb4 merge bitcoin#30270: update subtree to eb37a9b8 (Kittywhiskers Van Gogh)
ef10e83 Squashed 'src/minisketch/' changes from 3472e2f5ec..eb37a9b8e7 (Kittywhiskers Van Gogh)
94dca7f merge bitcoin#29823: update subtree to 3472e2f5e (Kittywhiskers Van Gogh)
9540ecb Squashed 'src/minisketch/' changes from a571ba20f9..3472e2f5ec (Kittywhiskers Van Gogh)

Pull request description:

  ## Additional information

  Unexpected failure was found in UBSan unit test run originating from minisketch tests ([build](https://gitlab.com/dashpay/dash/-/jobs/8206813511#L3512)), resolved in subtree with bitcoin-core/minisketch#81 and updated upstream in bitcoin#29823.  This pull request updates the subtree to latest subtree pulls done on upstream `master` (as of this writing, [`da10e0ba`](https://github.com/bitcoin/bitcoin/tree/da10e0bab4a3e98868dd663af02c43b1dc8b7f4a)).

  Special thanks to knst for reporting this bug! 🎉

  ## Breaking Changes

  None expected.

  ## Checklist

  - [x] I have performed a self-review of my own code
  - [x] I have commented my code, particularly in hard-to-understand areas **(note: N/A)**
  - [x] I have added or updated relevant unit/integration/functional/e2e tests **(note: N/A)**
  - [x] I have made corresponding changes to the documentation **(note: N/A)**
  - [x] I have assigned this pull request to a milestone _(for repository code-owners and collaborators only)_

ACKs for top commit:
  UdjinM6:
    utACK 5e65bb4

Tree-SHA512: be3c75436425c8662d6af46641a6fc744d01043a832884b29aa9767dd4b9090cef93bcb31355032131392a6ccf29cbbcb771a5786c654f26f4fa0a2d5f0e8a5f
tomt1664 pushed a commit to tomt1664/elements that referenced this pull request Apr 23, 2025
@fanquake
Merge bitcoin/bitcoin#29823: minisketch: update subtree to 3472e2f5ec…
6bea6f3 
…75ace39ce9243af6b3fee233a67492

4722b7c build: remove minisketch clz check (fanquake)
1eea10a Squashed 'src/minisketch/' changes from a571ba20f9..3472e2f5ec (fanquake)

Pull request description:

  bitcoin-core/minisketch#81 will fix #29799.
  Minor build cleanups after bitcoin-core/minisketch#80.

ACKs for top commit:
  dergoegge:
    utACK 4722b7c
  hebasto:
    ACK 4722b7c, I have verified the subtree update and reviewed the build system changes. Both look OK.

Tree-SHA512: eabd82e5a13cc4f32155319df97368f2e8c93320a4265b6c372efcb1ea4e756f6693df7c02498c8ea989ccd376a20277fa110c66d0754cb9bca5e54d18e0a965
tomt1664 pushed a commit to tomt1664/elements that referenced this pull request Apr 24, 2025
@fanquake
Merge bitcoin/bitcoin#29823: minisketch: update subtree to 3472e2f5ec…
3a1d2b0 
…75ace39ce9243af6b3fee233a67492

4722b7c build: remove minisketch clz check (fanquake)
1eea10a Squashed 'src/minisketch/' changes from a571ba20f9..3472e2f5ec (fanquake)

Pull request description:

  bitcoin-core/minisketch#81 will fix #29799.
  Minor build cleanups after bitcoin-core/minisketch#80.

ACKs for top commit:
  dergoegge:
    utACK 4722b7c
  hebasto:
    ACK 4722b7c, I have verified the subtree update and reviewed the build system changes. Both look OK.

Tree-SHA512: eabd82e5a13cc4f32155319df97368f2e8c93320a4265b6c372efcb1ea4e756f6693df7c02498c8ea989ccd376a20277fa110c66d0754cb9bca5e54d18e0a965
tomt1664 pushed a commit to tomt1664/elements that referenced this pull request Apr 24, 2025
Squashed 'src/minisketch/' changes from a571ba20f9..3472e2f5ec
6e0b07d 
3472e2f5ec Merge bitcoin-core/minisketch#81: Avoid overflowing shift by special casing inverse of 1
653d8b2e26 Avoid overflowing shift by special casing inverse of 1
33b7c200b9 Merge bitcoin-core/minisketch#80: Add c++20 version of CountBits
4a48f31a37 Merge bitcoin-core/minisketch#83: ci: Fix "s390x (big-endian)" task
82b6488acb Add c++20 version of CountBits
0498084d31 ci: Fix "s390x (big-endian)" task
71709dca9e Merge bitcoin-core/minisketch#82: ci: Fix `x86_64-w64-mingw32` task
9e6127fa98 Merge bitcoin-core/minisketch#74: Avoid >> above type width in BitWriter
ed420bc170 ci: Fix `x86_64-w64-mingw32` task
fe1040f227 Drop -Wno-shift-count-overflow compile flag
154bcd43bd Avoid >> above type width in BitWriter
67b87acdb6 Merge bitcoin-core/minisketch#78: ci: Update macOS image for CI
7de7250416 ci: Update macOS image for CI
83d812ea9f Merge bitcoin-core/minisketch#73: ci: Use correct variable to designate C++ compiler
e051a7d690 ci: Install wine32 package for Windows tests
2d2c695d78 build: Drop unused `CC` variable
1810fcbd11 ci: Use correct variable to designate C++ compiler
022b959049 Merge bitcoin-core/minisketch#77: Add missing include
08443c4892 Add missing include

git-subtree-dir: src/minisketch
git-subtree-split: 3472e2f5ec75ace39ce9243af6b3fee233a67492
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@sipa @theuni