> int32_t a1 = (int32_t) a; > int32_t b1 = (int32_t) b; > int32_t res1 = a1 * b1; > > If this is called with a and b equal to 0xffff, the 32-bit signed > multiplication will overflow - it is undefined behaviour. >Since you want only 32bit of the result, this is correct. You get incorrect results only if you use full multiplication (64bit result) with different unsigned/signed operation/result. When the result of a multiplication has the same size as the operands, the result is correct regardless signed/unsigned of any operands, including the result. This may be counter-intuitive unless you know what you are doing. You must remember that a multiplication always gives a double product, so taking only the low part gives you ... the low part.
C++ problem
Started by ●March 1, 2016
Reply by ●March 2, 20162016-03-02
Reply by ●March 2, 20162016-03-02
On 02/03/16 11:50, raimond.dragomir@gmail.com wrote:>> int32_t a1 = (int32_t) a; >> int32_t b1 = (int32_t) b; >> int32_t res1 = a1 * b1; >> >> If this is called with a and b equal to 0xffff, the 32-bit signed >> multiplication will overflow - it is undefined behaviour. >> > Since you want only 32bit of the result, this is correct. You get incorrect > results only if you use full multiplication (64bit result) with different > unsigned/signed operation/result.No, it is not correct - it is undefined behaviour. As signed 32-bit ints, 0xffff * 0xffff would be an overflow, and therefore undefined behaviour. Operations like that are not defined as nice two's complement arithmetic in C (even though in practice, that is what the compiler would probably generate).> > When the result of a multiplication has the same size as the operands, the > result is correct regardless signed/unsigned of any operands, including the > result. This may be counter-intuitive unless you know what you are doing. > You must remember that a multiplication always gives a double product, so > taking only the low part gives you ... the low part.It has nothing to do with that (I understand how multiplication works in this context, though I appreciate that not everyone does). The point to be aware of here is that operations on unsigned types smaller than "int" are promoted to /signed/ int before the operation is carried out. That can mean you get unexpected undefined behaviour due to /signed/ overflows, even though /unsigned/ overflow is fully defined in C (and C++). The point is subtle, and it is unlikely to be an issue in practice. But I think it is worth mentioning these details.
Reply by ●March 2, 20162016-03-02
miercuri, 2 martie 2016, 14:45:34 UTC+2, David Brown a scris:> On 02/03/16 11:50, raimond.dragomir@gmail.com wrote: > >> int32_t a1 = (int32_t) a; > >> int32_t b1 = (int32_t) b; > >> int32_t res1 = a1 * b1; > >> > >> If this is called with a and b equal to 0xffff, the 32-bit signed > >> multiplication will overflow - it is undefined behaviour. > >> > > Since you want only 32bit of the result, this is correct. You get incorrect > > results only if you use full multiplication (64bit result) with different > > unsigned/signed operation/result. > > No, it is not correct - it is undefined behaviour. As signed 32-bit > ints, 0xffff * 0xffff would be an overflow, and therefore undefined > behaviour. Operations like that are not defined as nice two's > complement arithmetic in C (even though in practice, that is what the > compiler would probably generate). > > > > > When the result of a multiplication has the same size as the operands, the > > result is correct regardless signed/unsigned of any operands, including the > > result. This may be counter-intuitive unless you know what you are doing. > > You must remember that a multiplication always gives a double product, so > > taking only the low part gives you ... the low part. > > It has nothing to do with that (I understand how multiplication works in > this context, though I appreciate that not everyone does). The point to > be aware of here is that operations on unsigned types smaller than "int" > are promoted to /signed/ int before the operation is carried out. That > can mean you get unexpected undefined behaviour due to /signed/ > overflows, even though /unsigned/ overflow is fully defined in C (and C++). > > The point is subtle, and it is unlikely to be an issue in practice. But > I think it is worth mentioning these details.Sorry, maybe I don't understand your point. I basically said that taking the low part gives correct result. In the very example given, 0xffff (16bit initially) * 0xffff (16bit) gives the 0x0001 result (16bit). What 16bit result would you expect? This result is correct in both cases (a 16bit operation (if available) and a converted operation with signed 32bit integers). Can you give an example where the conversion of an unsigned to the bigger signed type and then the multiplied result of the signed numbers truncated back is wrong?
Reply by ●March 2, 20162016-03-02
On 02.3.2016 г. 15:17, raimond.dragomir@gmail.com wrote:> miercuri, 2 martie 2016, 14:45:34 UTC+2, David Brown a scris: >> On 02/03/16 11:50, raimond.dragomir@gmail.com wrote: >>>> int32_t a1 = (int32_t) a; >>>> int32_t b1 = (int32_t) b; >>>> int32_t res1 = a1 * b1; >>>> >>>> If this is called with a and b equal to 0xffff, the 32-bit signed >>>> multiplication will overflow - it is undefined behaviour. >>>> >>> Since you want only 32bit of the result, this is correct. You get incorrect >>> results only if you use full multiplication (64bit result) with different >>> unsigned/signed operation/result. >> >> No, it is not correct - it is undefined behaviour. As signed 32-bit >> ints, 0xffff * 0xffff would be an overflow, and therefore undefined >> behaviour. Operations like that are not defined as nice two's >> complement arithmetic in C (even though in practice, that is what the >> compiler would probably generate). >> >>> >>> When the result of a multiplication has the same size as the operands, the >>> result is correct regardless signed/unsigned of any operands, including the >>> result. This may be counter-intuitive unless you know what you are doing. >>> You must remember that a multiplication always gives a double product, so >>> taking only the low part gives you ... the low part. >> >> It has nothing to do with that (I understand how multiplication works in >> this context, though I appreciate that not everyone does). The point to >> be aware of here is that operations on unsigned types smaller than "int" >> are promoted to /signed/ int before the operation is carried out. That >> can mean you get unexpected undefined behaviour due to /signed/ >> overflows, even though /unsigned/ overflow is fully defined in C (and C++). >> >> The point is subtle, and it is unlikely to be an issue in practice. But >> I think it is worth mentioning these details. > > Sorry, maybe I don't understand your point. I basically said that taking the > low part gives correct result. In the very example given, 0xffff (16bit initially) > * 0xffff (16bit) gives the 0x0001 result (16bit). What 16bit result would > you expect? > This result is correct in both cases (a 16bit operation (if available) > and a converted operation with signed 32bit integers). > > Can you give an example where the conversion of an unsigned to the bigger > signed type and then the multiplied result of the signed numbers truncated > back is wrong? > >I suppose he means that you do get the correct result by ignoring the overflow, which after all is not the correct result. $ffff unsigned expands to 32 bit $0000ffff signed, $ffff signed expands to $ffffffff signed. The signed product of these is $ffff0001, which does not fit in 16 bits, it takes 17 bits at least. Hardly a huge issue if one knows what he is doing, but if you rely on a compiler to know these things for you it can't be just dismissed. Dimiter ------------------------------------------------------ Dimiter Popoff, TGI http://www.tgi-sci.com ------------------------------------------------------ http://www.flickr.com/photos/didi_tgi/
Reply by ●March 2, 20162016-03-02
> $ffff unsigned expands to 32 bit $0000ffff signed, $ffff signed > expands to $ffffffff signed. The signed product of these is $ffff0001, > which does not fit in 16 bits, it takes 17 bits at least. > Hardly a huge issue if one knows what he is doing, > but if you rely on a compiler to know these things for you it can't > be just dismissed. > > Dimiter > > ------------------------------------------------------ > Dimiter Popoff, TGI http://www.tgi-sci.com > ------------------------------------------------------ > http://www.flickr.com/photos/didi_tgi/0000ffff * 0000ffff = fffe0001 0000ffff * ffffffff = ffff0001 ffffffff * ffffffff = 00000001 Taking the 16bit part: 0001 Which is what I said in the first place: regardless the signed/unsigned operands, you get the same "correct" result. I say "correct" because you DO ignore the overflow. The operands and the result are the SAME SIZE.
Reply by ●March 2, 20162016-03-02
On 02/03/16 14:17, raimond.dragomir@gmail.com wrote:> miercuri, 2 martie 2016, 14:45:34 UTC+2, David Brown a scris: >> On 02/03/16 11:50, raimond.dragomir@gmail.com wrote: >>>> int32_t a1 = (int32_t) a; >>>> int32_t b1 = (int32_t) b; >>>> int32_t res1 = a1 * b1; >>>> >>>> If this is called with a and b equal to 0xffff, the 32-bit signed >>>> multiplication will overflow - it is undefined behaviour. >>>> >>> Since you want only 32bit of the result, this is correct. You get incorrect >>> results only if you use full multiplication (64bit result) with different >>> unsigned/signed operation/result. >> >> No, it is not correct - it is undefined behaviour. As signed 32-bit >> ints, 0xffff * 0xffff would be an overflow, and therefore undefined >> behaviour. Operations like that are not defined as nice two's >> complement arithmetic in C (even though in practice, that is what the >> compiler would probably generate). >> >>> >>> When the result of a multiplication has the same size as the operands, the >>> result is correct regardless signed/unsigned of any operands, including the >>> result. This may be counter-intuitive unless you know what you are doing. >>> You must remember that a multiplication always gives a double product, so >>> taking only the low part gives you ... the low part. >> >> It has nothing to do with that (I understand how multiplication works in >> this context, though I appreciate that not everyone does). The point to >> be aware of here is that operations on unsigned types smaller than "int" >> are promoted to /signed/ int before the operation is carried out. That >> can mean you get unexpected undefined behaviour due to /signed/ >> overflows, even though /unsigned/ overflow is fully defined in C (and C++). >> >> The point is subtle, and it is unlikely to be an issue in practice. But >> I think it is worth mentioning these details. > > Sorry, maybe I don't understand your point. I basically said that taking the > low part gives correct result. In the very example given, 0xffff (16bit initially) > * 0xffff (16bit) gives the 0x0001 result (16bit). What 16bit result would > you expect? > This result is correct in both cases (a 16bit operation (if available) > and a converted operation with signed 32bit integers). > > Can you give an example where the conversion of an unsigned to the bigger > signed type and then the multiplied result of the signed numbers truncated > back is wrong? >I don't disagree with your desired results - multiplying 0xffff by 0xffff using uint16_t, one would expect a result of 0x0001 as a uint16_t. The issue is that the logical process of doing this multiplication involves undefined behaviour in C. As I noted earlier (but you snipped), the logical operation in C, once all integer promotions and arithmetic conversions are made explicit, is this: uint16_t mult16(uint16_t a, uint16_b) { int32_t a1 = (int32_t) a; int32_t b1 = (int32_t) b; int32_t res1 = a1 * b1; uint16_t res = ((uint32_t) res1) & 0xffff; return res; } (As before, we are assuming 32-bit int, and nice two's complement representation - no "weird" architectures.) If you want chapter and verse, the references here are to the C11 standard. The final draft version, N1570, is freely found on the net. 1. First, the uint16_t objects get integer promotion to "int" (6.3.2). Thus values (uint16_t) 0xffff become (int32_t) 0xffff. (Technically, "int32_t" does not have to be the same as "int" - it could be "long". But I'll call it "int32_t" to make the sizes clear.) 2. Then the calculation is done as a 32-bit signed integer multiplication. (Note that this is the /logical/ operation, required by the C standards. The compiler can optimise this to a different unsigned operation if it wants as long as the results are the same.) 3. This 32-bit signed int result "res1" is then converted to a uint16_t by repeatedly adding or subtracting 0x10000 until it is in the range 0 .. 0xffff. (6.3.1.3p2) This is the final value of the multiplication. It is at stage 2 that we have a problem. The operation is to multiply two 32-bit signed integers, each of value 0xffff. This is impossible within the realm of 32-bit signed integers - the mathematically correct result of 0xffff0001 cannot be represented as an int32_t (that bit-pattern corresponds to -65535, which is a different number). Thus it falls foul of 6.5p5 - "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.". What will the compiler do when it sees such undefined behaviour? Probably nothing - it is likely that multiplying two uint16_t will generate exactly the code you would expect all along. But you /could/ get unexpected behaviour, especially if inlining and/or constant propagation passes mean that the compiler could see the values of "a" and "b" at compile time, and knows that there is going to be undefined behaviour during the calculation. What is a little more likely with the integer promotion rules is not nasal daemons due to such undefined behaviour, but unexpected behaviour nonetheless. For example, given this code: uint16_t foo1(void) { uint16_t a = 0xffff; uint16_t b = 0xffff; return a * b; } A compiler will typically optimise this to "return 1;". It /could/ return any value it wanted, since the behaviour is undefined, but compiler writers go out of their way to produce efficient code, rather than actively annoying code. On the other hand, this code: bool foo2(void) { uint16_t a = 0xffff; uint16_t b = 0xffff; return (a * b) > 0; } will typically optimise to "return false;". So the same expression "a * b" looks like 1 in the first function, but is not greater than 0 in the second function. It all makes sense when you remember that (a * b) is a 32-bit signed integer expression, even though "a" and "b" are unsigned 16-bit types.
Reply by ●March 2, 20162016-03-02
On 02/03/16 15:08, Dimiter_Popoff wrote:> On 02.3.2016 г. 15:17, raimond.dragomir@gmail.com wrote: >> miercuri, 2 martie 2016, 14:45:34 UTC+2, David Brown a scris: >>> On 02/03/16 11:50, raimond.dragomir@gmail.com wrote: >>>>> int32_t a1 = (int32_t) a; >>>>> int32_t b1 = (int32_t) b; >>>>> int32_t res1 = a1 * b1; >>>>> >>>>> If this is called with a and b equal to 0xffff, the 32-bit signed >>>>> multiplication will overflow - it is undefined behaviour. >>>>> >>>> Since you want only 32bit of the result, this is correct. You get >>>> incorrect >>>> results only if you use full multiplication (64bit result) with >>>> different >>>> unsigned/signed operation/result. >>> >>> No, it is not correct - it is undefined behaviour. As signed 32-bit >>> ints, 0xffff * 0xffff would be an overflow, and therefore undefined >>> behaviour. Operations like that are not defined as nice two's >>> complement arithmetic in C (even though in practice, that is what the >>> compiler would probably generate). >>> >>>> >>>> When the result of a multiplication has the same size as the >>>> operands, the >>>> result is correct regardless signed/unsigned of any operands, >>>> including the >>>> result. This may be counter-intuitive unless you know what you are >>>> doing. >>>> You must remember that a multiplication always gives a double >>>> product, so >>>> taking only the low part gives you ... the low part. >>> >>> It has nothing to do with that (I understand how multiplication works in >>> this context, though I appreciate that not everyone does). The point to >>> be aware of here is that operations on unsigned types smaller than "int" >>> are promoted to /signed/ int before the operation is carried out. That >>> can mean you get unexpected undefined behaviour due to /signed/ >>> overflows, even though /unsigned/ overflow is fully defined in C (and >>> C++). >>> >>> The point is subtle, and it is unlikely to be an issue in practice. But >>> I think it is worth mentioning these details. >> >> Sorry, maybe I don't understand your point. I basically said that >> taking the >> low part gives correct result. In the very example given, 0xffff >> (16bit initially) >> * 0xffff (16bit) gives the 0x0001 result (16bit). What 16bit result would >> you expect? >> This result is correct in both cases (a 16bit operation (if available) >> and a converted operation with signed 32bit integers). >> >> Can you give an example where the conversion of an unsigned to the bigger >> signed type and then the multiplied result of the signed numbers >> truncated >> back is wrong? >> >> > > I suppose he means that you do get the correct result by ignoring the > overflow, which after all is not the correct result. > > $ffff unsigned expands to 32 bit $0000ffff signed, $ffff signed > expands to $ffffffff signed. The signed product of these is $ffff0001, > which does not fit in 16 bits, it takes 17 bits at least. > Hardly a huge issue if one knows what he is doing, > but if you rely on a compiler to know these things for you it can't > be just dismissed. >No, the issue is that the signed product 0xffffffff does not fit in a signed 32-bit integer - and that is undefined behaviour. This intermediary value exists logically before the conversion to 16-bit unsigned by modulo arithmetic.
Reply by ●March 2, 20162016-03-02
On 02.3.2016 г. 16:50, David Brown wrote:> On 02/03/16 15:08, Dimiter_Popoff wrote: >> On 02.3.2016 г. 15:17, raimond.dragomir@gmail.com wrote: >>> miercuri, 2 martie 2016, 14:45:34 UTC+2, David Brown a scris: >>>> On 02/03/16 11:50, raimond.dragomir@gmail.com wrote: >>>>>> int32_t a1 = (int32_t) a; >>>>>> int32_t b1 = (int32_t) b; >>>>>> int32_t res1 = a1 * b1; >>>>>> >>>>>> If this is called with a and b equal to 0xffff, the 32-bit signed >>>>>> multiplication will overflow - it is undefined behaviour. >>>>>> >>>>> Since you want only 32bit of the result, this is correct. You get >>>>> incorrect >>>>> results only if you use full multiplication (64bit result) with >>>>> different >>>>> unsigned/signed operation/result. >>>> >>>> No, it is not correct - it is undefined behaviour. As signed 32-bit >>>> ints, 0xffff * 0xffff would be an overflow, and therefore undefined >>>> behaviour. Operations like that are not defined as nice two's >>>> complement arithmetic in C (even though in practice, that is what the >>>> compiler would probably generate). >>>> >>>>> >>>>> When the result of a multiplication has the same size as the >>>>> operands, the >>>>> result is correct regardless signed/unsigned of any operands, >>>>> including the >>>>> result. This may be counter-intuitive unless you know what you are >>>>> doing. >>>>> You must remember that a multiplication always gives a double >>>>> product, so >>>>> taking only the low part gives you ... the low part. >>>> >>>> It has nothing to do with that (I understand how multiplication works in >>>> this context, though I appreciate that not everyone does). The point to >>>> be aware of here is that operations on unsigned types smaller than "int" >>>> are promoted to /signed/ int before the operation is carried out. That >>>> can mean you get unexpected undefined behaviour due to /signed/ >>>> overflows, even though /unsigned/ overflow is fully defined in C (and >>>> C++). >>>> >>>> The point is subtle, and it is unlikely to be an issue in practice. But >>>> I think it is worth mentioning these details. >>> >>> Sorry, maybe I don't understand your point. I basically said that >>> taking the >>> low part gives correct result. In the very example given, 0xffff >>> (16bit initially) >>> * 0xffff (16bit) gives the 0x0001 result (16bit). What 16bit result would >>> you expect? >>> This result is correct in both cases (a 16bit operation (if available) >>> and a converted operation with signed 32bit integers). >>> >>> Can you give an example where the conversion of an unsigned to the bigger >>> signed type and then the multiplied result of the signed numbers >>> truncated >>> back is wrong? >>> >>> >> >> I suppose he means that you do get the correct result by ignoring the >> overflow, which after all is not the correct result. >> >> $ffff unsigned expands to 32 bit $0000ffff signed, $ffff signed >> expands to $ffffffff signed. The signed product of these is $ffff0001, >> which does not fit in 16 bits, it takes 17 bits at least. >> Hardly a huge issue if one knows what he is doing, >> but if you rely on a compiler to know these things for you it can't >> be just dismissed. >> > > No, the issue is that the signed product 0xffffffff does not fit in a > signed 32-bit integer - and that is undefined behaviour. This > intermediary value exists logically before the conversion to 16-bit > unsigned by modulo arithmetic. > >David, the product is not $ffffffff - how did you arrive at that? Dimiter
Reply by ●March 2, 20162016-03-02
On 02.3.2016 г. 16:42, raimond.dragomir@gmail.com wrote:>> $ffff unsigned expands to 32 bit $0000ffff signed, $ffff signed >> expands to $ffffffff signed. The signed product of these is $ffff0001, >> which does not fit in 16 bits, it takes 17 bits at least. >> Hardly a huge issue if one knows what he is doing, >> but if you rely on a compiler to know these things for you it can't >> be just dismissed. >> >> Dimiter >> >> ------------------------------------------------------ >> Dimiter Popoff, TGI http://www.tgi-sci.com >> ------------------------------------------------------ >> http://www.flickr.com/photos/didi_tgi/ > > 0000ffff * 0000ffff = fffe0001 > 0000ffff * ffffffff = ffff0001 > ffffffff * ffffffff = 00000001 > Taking the 16bit part: 0001 > > Which is what I said in the first place: regardless the signed/unsigned > operands, you get the same "correct" result. > I say "correct" because you DO ignore the overflow. The operands and the > result are the SAME SIZE. >Hmmmm, but 0001 does not equal ffff0001. The result would be correct it we state it as (-1)*($ffff)!.$ffff (!. being logical and, $ffff being unsigned and -1 being signed, 32 bit all 1. ). IOW, (-1)*(-1) is 1, both input numbers being signed; but -1*65535 (just the -1 being signed) is -65535 or $10001 . Like you say it is all about ignoring the overflow, if you are OK with that of course you get the correct result - but it is not just multiplication in that case, there is also the AND above. Dimiter
Reply by ●March 2, 20162016-03-02
On 03/01/2016 04:12 PM, Tim Wescott wrote:> On Tue, 01 Mar 2016 21:02:46 +0000, tim... wrote: > >> Today, I discovered that if you use: >> >> const unsigned int xxx = value; (which in this case happens to be >> = 0) >> >> and then in the code try and compare it with a signed int yyy >> >> the compiler ignores your signed int and does an unsigned compare. >> >> Up until now this hadn't been a problem as I've (quite by chance) >> always looked for equality with the const. >> >> But today I counted yyy down to -1 wishing to stop when yyy < xxx >> but the sodding compiler decided that I now had a very large >> positive number and refused to break from my loop. >> >> Took me flipping ages to work out what was wrong :-( >> >> The compiler does give me a warning - that I am comparing a signed >> with an unsigned but as I was sure that the unsigned int was the >> zero value const I didn't give it a second thought. >> >> But I did get rid of it by using a c-style cast to make the >> unsigned int a signed one when comparing, and that suppressed the >> warning, but it still didn't work. - not until I redefined my >> const as signed! >> >> I'm not hugely experienced with C++ [1], is it meant to work like >> this or do I have a broken compiler? >> >> We're using GCC >> >> TIA >> >> Tim >> >> [1] nor are any of my co-workers, finding good ones who will work >> for the pittance that embedded work now pays in my neck of the >> woods is tres difficult :-) > > 1: Yes, it's supposed to work like that. Google "automatic type > conversions".Yup, downcounting loops with unsigned loop counters is a classic bug. The OP will remember next time. ;) Signed ints don't have the problem, obviously, and this is one reason it's a bad idea to reuse loop counter variables, unless you're writing for an 8-bit MCU.> > 2: I'm pretty sure that C is supposed to work like that, too. If it > isn't, then the behavior is implementation defined -- meaning that > it won't be predictable at all.Since essentially all computers still crunching use twos-complement binary for signed ints, that behaviour is very nearly guaranteed. IIRC you can turn on integer overflow traps so that it behaves like a divide-by-zero, but a whole lot of software relies on this behaviour.> > 3: "by using a c-style cast to make the unsigned int a signed one > when comparing, and that suppressed the warning, but it still didn't > work. - not until I redefined my const as signed!" > > What? 'splain, please. I thought the const was the only unsigned. > > You should use a C++ - style cast: > > if (static_cast<int>(xxx) >= yyy) { yadda yadda } > > 4: Use -Wall. Then, since "all" does not, somehow, mean "all" to the > crew at GCC, use -Wextra, too.Yup. A copy of PC-Lint is helpful too (assuming they've kept it up to date--my copy doesn't understand anything past C++08.) Cheers Phil Hobbs -- Dr Philip C D Hobbs Principal Consultant ElectroOptical Innovations LLC Optics, Electro-optics, Photonics, Analog Electronics 160 North State Road #203 Briarcliff Manor NY 10510 hobbs at electrooptical dot net http://electrooptical.net
