32 bit unsigned multiply on 64 bit causing undefined behavior?

Question

So I have about this code:

uint32_t s1 = 0xFFFFFFFFU;
uint32_t s2 = 0xFFFFFFFFU;
uint32_t v;
...
v = s1 * s2; /* Only need the low 32 bits of the result */

In all the followings I assume the compiler couldn't have any preconceptions on the range of s1 or s2, the initializers only serving for an example above.

If I compiled this on a compiler with an integer size of 32 bits (such as when compiling for x86), no problem. The compiler would simply use s1 and s2 as uint32_t typed values (not being able to promote them further), and the multiplication would simply give the result as the comment says (modulo UINT_MAX + 1 which is 0x100000000 this case).

However if I compiled this on a compiler with an integer size of 64 bits (such as for x86-64), there might be undefined behavior from what I can deduce from the C standard. Integer promotion would see uint32_t can be promoted to int (64 bit signed), the multiplication would then attempt to multiply two int's, which, if they happen to have the values shown in the example, would cause an integer overflow, which is undefined behavior.

Am I correct with this and if so how would you avoid it in a sane way?

I spotted this question which is similar, but covers C++: What's the best C++ way to multiply unsigned integers modularly safely?. Here I would like to get an answer applicable to C (preferably C89 compatible). I wouldn't consider making a poor 32 bit machine potentially executing a 64 bit multiply an acceptable answer though (usually in code where this would be of concern, 32 bit performance might be more critical as typically those are the slower machines).

Note that the same problem can apply to 16 bit unsigned ints when compiled with a compiler having a 32 bit int size, or unsigned chars when compiled with a compiler having a 16 bit int size (the latter might be common with compilers for 8 bit CPUs: the C standard requires integers to be at least 16 bits, so a conforming compiler is likely affected).

Catalinacatalo

int is 32 bits even on most modern 64-bit architectures en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models – Multiply

What makes you think you have defined behaviour on a 32-bit machine? – Miguel

Originally I wrote it 16 bit vs. 32 bit, but then realized it might be more practical today to compare 32 vs. 64 bit. Charles: I assume by analyzing the C89 standard. I may be wrong, then point it out, in what! That's also an acceptable outcome / answer! – Catalinacatalo

@IdeaHat: Please look up the default integer promotions. – Spindlelegs

I only have an only C99 with me at the moment, but: 6.5/5 says "If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined." – Miguel

I counter with C99, 6.2.5/9. :) – Catalinacatalo

@Jubatian: sorry, I missed the unsignedness that was the whole point of your post. That makes things clearer to me. – Miguel

Oh come on. Is anything even defined in C? – Etching

@harold, yes: __STDC__ is. – Crossexamine

Thanks for the scare. I never realized that integer promotion interacted this way with unsigned arithmetic. I always took the lines about mod 2^n arithmetic at face value. – Dresden

@Tim: I posted it especially for that, although now even I realize that I might actually need to stroll through an entire project which is set up to be compiler int size independent (currently working fine on both 32 and 64 bits) to check for such multiplies and other stuff I took for granted. Proves you can just never know all the beasts lurking in the shadows of C... – Catalinacatalo

@TimSeguine Promotion from uint to int is acceptable if one of the operands is a wider int, however two uints converting to int is evil. – Gaylor

This issue also applies with uint16_t s1,s2 on 32-bit int machines. (and uint8_t s1,s2 on 16-bit int machines.) Also with other orators like '+', '-' and maybe '/', '%'. – Tynan

@chux: I even wrote it originally in 16 bit vs. 32 bit relation, but thanks, it's true I overlooked mentioning this! I fixed the question accordingly. Other operators however are not affected as far as I see, since they can't produce a big enough result to produce an overflow in the twice as wide promoted type. Not even shifts would be affected, due to their shift amount constraint (on 32 bits, you can shift at most 31 bits to the left, you just can not make stuff larger than 64 bit INT_MAX then). – Catalinacatalo

@Lưu Vĩnh Phúc: True, but it might even make the situation more dangerous if things actually start to break with a 64 bit int size compiler (which even as the Wiki article says, exist). You could build up a huge codebase with the false assumption it works fine on 64 bit (overlooking to check the actual int size of the compiler). – Catalinacatalo

"F U!" ... "Yeah? Well then. FFFFFFFFU!" – Plenteous

Your comment to @Lưu Vĩnh Phúc applied in the past with a large amount of 16-bit int code begin ported to 32-bit int. It's the same problem, just different sizes. – Tynan

@chux: It's a worse problem since the philosophy of most C compilers used to be that code like ushort3=ushort1*ushort2; should yield the "natural" (mod-65536) result absent some reason why it shouldn't, but the hyper-modern philosophy is that compilers are entitled to use the fact that ushort1*ushort2 "can't" be bigger than INT_MAX to prune any code paths which would only occur if the product were larger than INT_MAX. – Scuppernong

Answer 1

The simplest way to get the multiplication to happen in an unsigned type that is at least uint32_t, and also at least unsigned int, is to involve an expression of type unsigned int.

v = 1U * s1 * s2;

This either converts 1U to uint32_t, or s1 and s2 to unsigned int, depending on what's appropriate for your particular platform.

@Deduplicator comments that some compilers, where uint32_t is narrower than unsigned int, may warn about the implicit conversion in the assignment, and notes that such warnings are likely suppressable by making the conversion explicit:

v = (uint32_t) (1U * s1 * S2);

It looks a bit less elegant, in my opinion, though.

Comptom

@Spindlelegs That happens implicitly, since v is defined as uint32_t. – Comptom

Huh, this answer seems quite elegant... Which should I choose, which should I choose... :) – Catalinacatalo

@Spindlelegs I'm not sure I agree that it's necessarily good for a compiler to warn for this, but I do agree that it is likely that there are compilers that warn for it. Will add a note. – Comptom

@hvd This works because multiply is from left-to-right, right? If 1U was all the way on the right, the first multiplication would still be s1 * s2 and converted to int. – Gaylor

@Gaylor That's correct. 1U * s1 * s2 always means (1U * s1) * s2, and s1 * s2 * 1U always means (s1 * s2) * 1U. An alternative that just might be slightly more readable, by not requiring the reader to know how * binds, would be s1 * 1U * s2. – Comptom

If a compiler always warned about narrowing with v = s1 *s2, then that is a good thing for that means this 1u * fix is needed. – Tynan

Oh crap, now I need to write cross-platform macros for multiplication too. – Indogermanic

Answer 2

Congratulations on finding a friction point.

A possible way:

v = (uint32_t) (UINT_MAX<=0xffffffff
  ? s1 * s2
  : (unsigned)s1 * (unsigned)s2);

Anyway, looks like adding some typedefs to <stdint.h> for types guaranteed to be no smaller than int would be in order ;-).

Spindlelegs

Does it even need the conditional? I assume it would play OK as simply v = (unsigned)s1 * (unsigned)s2;, the type of v would take care of the proper truncating anyway, while on 32 bits, it is still a 32 bit multiply. At least if I except unsigned to be at least 32 bits... Wait, aren't there such types already defined? – Catalinacatalo

Trouble is, int need not have more than 16 bits... And no, there are no such types. – Spindlelegs

Eh, sorry for being vague, I meant 32 bit int compiler... Well, the type I mean is uint_least32_t in stdint.h, a suitable substitution may even be ifdeffed for C89 I guess. – Catalinacatalo

does this work with 1's complement or sign-magnitude? – Multiply

@LưuVĩnhPhúc: For unsigned numbers, those terms are meaningless. – Spindlelegs