`primeSieve(31627)` reads past the precomputed prime table
Nobody has claimed this yet.
Assessment
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Newbie friendliness
- 72/100
Research direction
Start in src/Eratosthenes.cpp, in the table shortcut loop at lines 66-72 of PrimeSieveSmall(): compare ind against the actual length of smallPrimeBase so traversal stops at the boundary while still emitting 31,627. Then extend the existing R test that uses primeSieve(31625, 31630) with endpoint cases at 31,627 and its neighbours, in the package's testthat suite. Done means the endpoint test passes under ordinary build and under AddressSanitizer, with no read past the array.
Written by the indexing model from the issue text.
Description
PrimeSieveSmall() reads beyond smallPrimeBase when the upper bound equals the table’s final entry, 31,627.
The affected R call is:
RcppAlgos::primeSieve(31627)
The table shortcut uses this loop:
After emitting the final prime, ind becomes 3402. The next condition reads element 3402 of the 3402-element array.
This is undefined behavior, even when an ordinary build appears to return the expected primes.
Verification
A standalone build of the unchanged native implementation, using Apple Clang 17 with AddressSanitizer, reported a global-buffer-overflow: a four-byte read immediately after smallPrimeBase.
The native reproduction called PrimeSieve::PrimeSieveMain<int> with bounds 1, 31627, one thread, and initially empty output vectors. The sanitizer finding was reproduced through this native entry point, rather than an installed R package.
Expected behavior and follow-up
- Stop traversal at the table boundary while including 31,627 in the result.
- Add regression coverage for the exact endpoint and relevant nearby bounds.
- Verify the correction under AddressSanitizer as well as ordinary tests.
The existing primeSieve(31625, 31630) test takes a different path and does not cover this boundary.
- Dominant language
- C++
- Stars
- 51
- Forks
- 5
- Avg merge
- 6h 55m
- Merged PRs (30d)
- 8
Getting set up
This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from jwood000/RcppAlgos
-
Difficulty 3/5 1-2 days Newbie friendliness 45/100
-
Non-repeated and non-duplicated combinations from groups with varying sizes that contain overlapsOpenenhancement
Difficulty 5/5 Over a week Newbie friendliness 25/100
-
Multiset partitionsOpen
Difficulty 3/5 1-2 days Newbie friendliness 30/100
-
Combinatorial Iterators not working parallelMay be free again @jwood000 claimed this 1689 days ago, and no pull request is open. Openenhancement
-
Difficulty 5/5 Over a week Newbie friendliness 25/100
All issues in jwood000/RcppAlgos
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 65/100
scp-fs2open/fs2open.github.com#7965 ·
Maintainers usually reply within 1 day
-
[Bug][CuTeDSL][Fuzz] `utils.gemm.sm100.epilogue` releases the accumulator before `tcgen05.ld` completes: no `tcgen05.wait::ld` before the arrive that lets the next MMA overwrite TMEMPossibly taken A pull request linked to this issue is open or already merged. Open
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
Maintainers usually reply within 4 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
elf-alchemist/elfbsp#113 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
patrick-hudson/put.gd-desktop#979 · 1 comment ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
Dao-AILab/flash-attention#3097 ·
Maintainers usually reply within 3 days