warning C4307: “*” on VS2017

[soncfe]

build in spdlog 1.11.0 header only,

spdlog\fmt\bundled\format-inl.h(1154): warning C4307: “*”

// Remove trailing zeros from n and return the number of zeros removed (float)
FMT_INLINE int remove_trailing_zeros(uint32_t& n) noexcept {
FMT_ASSERT(n != 0, "");
const uint32_t mod_inv_5 = 0xcccccccd;
const uint32_t mod_inv_25 = mod_inv_5 * mod_inv_5; //// ?????

[vitaut]

I wasn't able to reproduce this in https://godbolt.org/z/baaGbjebz. Please provide more repro details.

[vitaut]

Closing for now but feel free to reopen with a repro (ideally on godbolt).

[Qujamlee]

I wasn't able to reproduce this in https://godbolt.org/z/baaGbjebz. Please provide more repro details.

There is indeed this problem, and I have reproduced it on the website you provided, but you need to choose x64msvc19.22 and earlier versions of the compiler.I copied the warning message:

x64 msvc v19.22 /std:c++latest /W2
Compiler stdout
example.cpp

(5): warning C4307: '*': integral constant overflow Program returned: 0

But using newer versions of the compiler does not have this warning. Why? Did the compiler do the optimization?
I'm doing the math,
const uint32_t mod_inv_5 = 0xcccccccd = 3_435_973_837 (decimal),
the square of it is 11_805_916_208_548_502_569,
It does exceed the maximum range of uint32_t (4_294_967_295) ,
so the warning message seems reasonable, is it a bug?

[vitaut]

@jk-jeon, what is the logic behind

fmt/include/fmt/format-inl.h

Lines 1183 to 1184 in 115ca96

	const uint32_t mod_inv_5 = 0xcccccccd;
	const uint32_t mod_inv_25 = mod_inv_5 * mod_inv_5;

?

Would it make sense to avoid overflow there?

[jk-jeon]

0xcccccccd is the modular inverse of 5 (mod $2^{32}$ ), so the square of it is the modular inverse of 25. This is indeed an intended overflow. There are several ways I can think of to silence this warning:

1. Disable the warning. Preferably locally, if possible.
2. Write static_cast<uint32_t>(static_cast<uint64_t>(mod_inv_5) * mod_inv_5) instead. The result must be the same as now. But honestly, since the exact intention of the code is precisely the modular arithmetic, doing this feels like "why bother?" to me. Also, this doesn't generalize to the 64-bit version right below.
3. Ask Wolfram Alpha to compute (0xcccccccd * 0xcccccccd) mod 2^32 and write the result directly into the code. But I think this obfuscates the code a tiny bit, as it is relatively obvious that 0xcccccccd should be the modular inverse of 5, but it's harder to imagine what should be the modular inverse of 25.

And here is the logic behind the code.

Granlund-Montgomery, Section 9, explains that to check if an unsigned integer $n$ is a multiple of an odd number $g$, you multiply $n$ to the modular inverse of $g$ and then compare it against the largest possible number ( $2^{32}-1$ ) divided by $g$. If the latter is bigger than or equal to, then that means $n$ is a multiple of $g$. Otherwise, $n$ is not a multiple of $g$.

This is because multiplying $g$ is a one-to-one correspondence from the set $\{0,1,\ \cdots\ ,2^{32}-1\}$ onto itself, whose inverse map is given by the multiplication of the modular inverse. Since all the multiples of $g$ should be the image of one of $0,1,\ \cdots\ ,\left\lfloor(2^{32}-1)/g\right\rfloor$, anything other than those numbers should be mapped to a non-multiple of $g$. Hence, when multiplying the modular inverse of $g$, the result is at most $\left\lfloor(2^{32}-1)/g\right\rfloor$ if and only if $n$ is a multiple of $g$, and in that case the result must be exactly $n/g$.

Granlund-Montgomery also explains that, to check $n$ is a multiple of any number, not necessarily odd, we first decompose that number into $2^{t}g$ where $g$ is odd, then $n$ is a multiple of that number if and only if $n$ is a multiple of $g$ and $2^{t}$ at the same time. In this case, what we do is to multiply the modular inverse of $g$ and then compute the rotate-to-right of the result by $t$-bits. Then the resulting number will contain some $1$'s in the first $t$-bits if and only if $n$ is not a multiple of $2^{t}$. So we compare this to $\left\lfloor(2^{32}-1)/(2^{t}g)\right\rfloor$. Then,

• If $n$ is not a multiple of $2^{t}$, then some of the first $t$-bits should be $1$'s, but since all of the first $t$-bits of $\left\lfloor(2^{32}-1)/(2^{t}g)\right\rfloor$ must be $0$, the former should be strictly larger than the latter.
• If $n$ is a multiple of $2^{t}$, then what happens is that we are essentially comparing $n/2^{t}$ times the modular inverse of $g$, with respect to $2^{32-t}$ rather than $2^{32}$, versus $\left\lfloor (2^{32}-1)/(2^{t}g)\right\rfloor = \left\lfloor 2^{32}/(2^{t}g)\right\rfloor = \left\lfloor (2^{32-t}-1)/g\right\rfloor$. So the former is strictly larger than the latter if and only if $n/2^{t}$ is not a multiple of $g$, if and only if $n$ is not a multiple of $g$.
• If $n$ is a multiple of $2^{t}g$, then the rotate-to-right by $t$-bits we computed should be precisely equal to $n/(2^{t}g)$.

In our case, $t=2$ and $g=25$ so that $2^{t}g = 100$. So what's happening in the while loop is that we repeatedly check if $n$ is divisible by $100$ and divide it by $100$ if that is the case.

[vitaut]

Thanks, @jk-jeon, for the detailed explanation. Considering that unsigned overflow is well-defined and the warning appears to be a false positive fixed in more recent versions of MSVC, I don't think we need to do anything. It can still be suppressed using FMT_SYSTEM_HEADERS or some other method that doesn't involve changes to {fmt}.