C++ problem

On 03.3.2016 г. 11:00, Paul Rubin wrote:
> David Brown <david.brown@hesbynett.no> writes:
>> If you have 65535 people, and each of them eat 65535 jelly beans, they
>> have eaten 4294901761 jelly beans in total - they have not eaten -65535
>> beans.
>
> Um, 4294836225, but the point is well stated.
>

Um, so far two of you 5-th grade bound for the signed numbers lesson.

Dimiter_Popoff <dp@tgi-sci.com> writes:
> The product of SIGNED multiplication (as you repeatedly repeated) is
> a SIGNED number and $ffff0001 being a SIGNED number is -65535.

You can't multiply a positive number by a positive number and get a
negative number, except through overflow.  And in C, overflow on signed
ints results in UB.  

> Then in NO working compiler would the product of a signed 16 bit
> being -1 ($ffff) and an unsigned $ffff (65535) - being converted to
> signed prior to multiplication 

Where did signed $ffff come from?  I thought we were talking about
unsigned $ffff being multiplied by itself.

Regarding "no working compiler": we're discussing the dark corners of C,
and you have to define C as "what the standard says" rather than "what
compilers you've looked at happen to do".  If the standard says UB then
the code is invalid.  Real world C programs are full of such bugs by
the way:

   http://www.cs.utah.edu/~regehr/papers/tosem15.pdf

I'd like to try David's example with KCC, a deliberately sadistic C
interpreter that tries to trap as much UB as it can, for the purpose of
finding bugs in code:

  http://blog.regehr.org/archives/523

  https://github.com/kframework/c-semantics

On 03.3.2016 г. 11:26, Paul Rubin wrote:
> Dimiter_Popoff <dp@tgi-sci.com> writes:
>> The product of SIGNED multiplication (as you repeatedly repeated) is
>> a SIGNED number and $ffff0001 being a SIGNED number is -65535.
>
> You can't multiply a positive number by a positive number and get a
> negative number, except through overflow.  And in C, overflow on signed
> ints results in UB.
>
>> Then in NO working compiler would the product of a signed 16 bit
>> being -1 ($ffff) and an unsigned $ffff (65535) - being converted to
>> signed prior to multiplication
>
> Where did signed $ffff come from?  I thought we were talking about
> unsigned $ffff being multiplied by itself.

It was there from the very start of the thread and is present
throughout.

>
> Regarding "no working compiler": we're discussing the dark corners of C,
> and you have to define C as "what the standard says" rather than "what
> compilers you've looked at happen to do".  If the standard says UB then
> the code is invalid.  Real world C programs are full of such bugs by
> the way:

I know programs are full of bugs and I know legacy may keep wrong
operations alive for decades but I would be seriously stunned if
it turns out that in C (which I do not use, I use my vpa
obviously) multiplying these two constants, 16 bit $ffff representing
a signed number (i.e. being -1) and 16 bit $ffff unsigned (i.e.
65535) into a 32 bit result would not work. Then may be it would
not work indeed if they do not extend the operands to 32 bit prior
to the multiplication, a compiler writer beginners error but it could
well have persisted, I don't know that.
I obviously do know the basic arithmetic about it though and I
corrected David over his wrong figures and statements, that's all.

Dimiter

On 03/03/16 09:53, Dimiter_Popoff wrote:
> On 03.3.2016 г. 10:16, David Brown wrote:
>> On 03/03/16 06:07, Dimiter_Popoff wrote:
<snip>
>>> LOL, David.
>>> So you have yet to learn that the signed product of (-1)*(65535)
>>> (signed $ffff 16 bit * unsigned $ffff 16 bit) is -65535, representable
>>> in 32 bits as $ffff0001, does fit in a minimum of 17 bits and of course
>>> does fit in 32 bits.
>>>
>>
>> The product of uint16_t 0xffff and uint16_t 0xffff, on a 32-bit int
>> system, is undefined in C.  This is because the calculation is done as
>> 32-bit signed, and the value 0xfffe0001 (avoiding typos, I hope) is too
>> big for signed int32_t.  The value 0xfffe0001 is 4294901761 in decimal -
>> it is /not/ -65535.  Sure, you can fit -65535 into a signed int32_t - or
>> even an int17_t if you like.  But you cannot fit 4294901761 into a
>> signed int32_t.
> 
> David. Will you ever learn to stop digging when in a hole you have put
> yourself in.

I believe I have just spotted your problem.  My example of the
unexpected undefined behaviour in unsigned arithmetic was multiplying
/unsigned/ 16-bit 0xffff by /unsigned/ 16-bit 0xffff.  Somewhere along
the line, you have changed one of these to /signed/ 16-bit 0xffff.  Of
course there is no such number as signed 16-bit 0xffff - it is outside
the range for 16-bit signed integers.  But if you mean -1, which will
(on almost all systems) be represented by the bit pattern 0xffff, then
you are talking about a very different calculation:


uint16_t mult16su(int16_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;
}

When called with mult16su(-1, 0xffff), a1 is the 32-bit int value -1,
while b1 is the 32-bit int value 65535.  These can, of course, be
multiplied without integer overflow, to give -65535.  And when converted
to a uint16_t, the result is 0x0001 with no undefined behaviour.


I really should have spotted your misconception in your first post in
this thread, where you first wrote "$ffff unsigned expands to 32 bit
$0000ffff signed, $ffff signed expands to $ffffffff signed" instead of
using unsigned 16-bit values at each stage.  We have both failed to read
other posts accurately enough here.


Now, with that mistake corrected, you can go back a few posts and see if
you now understand my point.

On 02.3.2016 г. 16:47, David Brown wrote:
> 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.
>

David, all this is very nice and I was indeed quite explicit about
signed etc. in all my posts.

HOWEVER, your statement that $ffff*$ffff - both unsigned - results in
a 32 bit overflow is wrong - the result is $fffe0001, a perfectly
well 32 bit representable unsigned number.
Expecting a signed result from the multiplication of two unsigned
operands would be a laughable idea but in that case it would
overflow indeed. I leave it to you to clarify how the C language
would do this by default(unsigned16*unsigned16 -> ???32), I just
don't know (nor am I particularly interested in).

Dimiter

On 03/03/16 10:59, Dimiter_Popoff wrote:
> On 02.3.2016 г. 16:47, David Brown wrote:
>> 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.
>>
> 
> David, all this is very nice and I was indeed quite explicit about
> signed etc. in all my posts.
> 
> HOWEVER, your statement that $ffff*$ffff - both unsigned - results in
> a 32 bit overflow is wrong - the result is $fffe0001, a perfectly
> well 32 bit representable unsigned number.
> Expecting a signed result from the multiplication of two unsigned
> operands would be a laughable idea but in that case it would
> overflow indeed. I leave it to you to clarify how the C language
> would do this by default(unsigned16*unsigned16 -> ???32), I just
> don't know (nor am I particularly interested in).
> 

That's the way the C language works.  You can laugh about it (or indeed
cry about it, when it leads to wailing and gnashing of teeth), but
that's what C does.  Before any sort of arithmetic operation or
comparison, any types that are smaller than "int" get promoted to "int"
(that's a simplification, but good enough for now).  So on a 32-bit
system, uint16_t types get turned into int32_t types with the same
value, and then the operation is carried out.

You can force unsigned behaviour by simply casting one of the parts to
uint32_t, as in "(uint32_t) a * b", which will also ensure that b is
converted to an uint32_t (it passes through "int" on the way, but that
makes no difference).

I expect you will consider this one of the reasons you prefer assembly
to C, and there are many (myself included) who think the rules of C are
a bit weird here.  But we have to live with it.

On Thu, 3 Mar 2016 11:39:16 +0200, Dimiter_Popoff <dp@tgi-sci.com>
wrote:

>...  I would be seriously stunned if
>it turns out that in C (which I do not use, I use my vpa
>obviously) multiplying these two constants, 16 bit $ffff representing
>a signed number (i.e. being -1) and 16 bit $ffff unsigned (i.e.
>65535) into a 32 bit result would not work.

It's not just a question of whether it works ... it's also a question
of _why_ it works.  This behavior works de facto due to a quirk[*] of
implementation, not because the C standard says it should work.

[*] a ubiquitous quirk, but a quirk nonetheless.

George

On 3/3/2016 12:32 AM, Philip Lantz wrote:
> rickman wrote:
>>
>> On 3/2/2016 4:18 PM, Hans-Bernhard Br�ker wrote:
>>> Am 02.03.2016 um 00:50 schrieb rickman:
>>>> On 3/1/2016 5:20 PM, Hans-Bernhard Br�ker wrote:
>>>>> Am 01.03.2016 um 22:02 schrieb tim...:
>>>
>>>>>> 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!
>>>
>>>>> That attempt most probably failed in some other, unrelated way.  Which
>>>>> way it was can only be found out if you show an actual, essentially
>>>>> complete (as in: compilable) example case.
>>>>
>>>> That's easy.  He said he was counting down to -1 which won't work if the
>>>> value is cast to an unsigned.
>>>
>>> No, it's not that easy, because per his actual statement (see above) he
>>> did _not_ cast the signed -1 to unsigned in this try; he said he cast
>>> the const unsigned 0 to signed, instead.  That should have worked.
>>
>> Yes, I have it backwards.  So why didn't that work?
>
> I'm sure we could easily figure it out, but only if he shows us the code.

The OP has responded at least once, but no code.  Funny...

-- 

Rick

rickman wrote:

>
> Why would anyone need PC-Lint?  The compiler gave a warning about mixing 
> of data types.  It has been awhile since I programmed much in C, but 
> when I did I always programmed for zero warnings.
>
> I should do that in VHDL for FPGAs too, but oddly enough, some of the 
> warnings come in the steps that are vendor dependent and warnings are 
> generated by the things the tools do with no way to prevent the warnings 
> other than turning off reporting of warnings.  Stupid vendors!
>

God, I wish.  I write C, -Wall, -Wextra.  No warnings, all is good.  I
write perfectly good VHDL and I'll often wind up with a THOUSAND
warnings.

At one point I tried going through with an Awk script after the fact to
look for known warnings and suppress them from the output, but managing
the list of "known warnings" just got to be too much lift.

-- 
Rob Gaddi, Highland Technology -- www.highlandtechnology.com

Email address domain is currently out of order.  See above to fix.

On 3/3/2016 12:56 PM, Rob Gaddi wrote:
> rickman wrote:
>
>>
>> Why would anyone need PC-Lint?  The compiler gave a warning about mixing
>> of data types.  It has been awhile since I programmed much in C, but
>> when I did I always programmed for zero warnings.
>>
>> I should do that in VHDL for FPGAs too, but oddly enough, some of the
>> warnings come in the steps that are vendor dependent and warnings are
>> generated by the things the tools do with no way to prevent the warnings
>> other than turning off reporting of warnings.  Stupid vendors!
>>
>
> God, I wish.  I write C, -Wall, -Wextra.  No warnings, all is good.  I
> write perfectly good VHDL and I'll often wind up with a THOUSAND
> warnings.
>
> At one point I tried going through with an Awk script after the fact to
> look for known warnings and suppress them from the output, but managing
> the list of "known warnings" just got to be too much lift.

My projects tend to be on the small side so I can usually focus on the 
more important parts of the project earlier and deal with the warnings 
toward the end.  I do make sure I have vetted every warning before I 
release any design to a customer.  There are pitfalls in FPGA design and 
if the tools are telling me of any of them I want to utilize that.

Most of the warnings have to do with optimizing away logic that was 
added as part of a vendor supplied and utilized module that has 
functions which are unneeded.  When the unneeded outputs are optimized 
away a warning is reported.  Silly vendors.

-- 

Rick