exercism / cpp

Exercism exercises in C++.
https://exercism.org/tracks/cpp
MIT License
254 stars 207 forks source link

`int idx` --> `size_t idx` to prevent integer overflow #720

Closed tuan-karma closed 6 months ago

tuan-karma commented 11 months ago
for(int idx = number * number; idx <= limit; idx +=number)
    composite[idx] = true;

This code can be integer overflow if the limit > sqrt(maxInt). --> Then it leads to wrongly admit that idx <= limit. --> Then it leads to an out of bounds access at composite[idx] = true then it leads to Segmentation Fault (for example, when you set limit = 47000).

siebenschlaefer commented 11 months ago

Yes, there's a potential integer overflow if the limit is too big. Good catch!

But the suggested change doesn't fix that, the underlying type of the operation number * number is still int, you will still get an integer overflow if the limit is too big, before the conversion to std::size_t.
Also, I would recommend not to mix signed and unsigned types in the same expression (see C++CG).

How about defining number and idx as long long or std::int64_t? That should solve the problem, at least on platforms where an int has fewer than than 64 bits. What do you think?

vaeng commented 6 months ago

4 months have passed without a reaction from the original poster. I am thus merging it with SIebenschläfers suggestions. I hope that is okay. Tuan should still get reputation points on Exercism.