From: Andy 'Krazy' Glew on
On 6/26/2010 10:40 AM, EricP wrote:
> Andy 'Krazy' Glew wrote:
>>
>> Some examples:
>>
>
> You are really doing signed 9 bit arithmetic there,
> then casting the s9 result back to either a u8 or s8 type.
> Whether there is an overflow or not depends on the result
> type and the value.

Exactly.

And if I was doing the same in 16, 32, 64 bit arithmetic, I would be essentially doing the intermediate calculations in
17, 33, 65 bits, and casting back.

And, since support for 9, 17, 33, 65 bits is not ubiquitous, and since doubling the width to 8, 32, 64 bits, which is
ubiquitous, tends to cost a lot in performance (let alone the fact that extending precision from 64 bits, whether to 65
bits or 128 bits, is not ubiquitous), I am looking for expressions that allow detection of overflow based on modulo
arithmetic.

Although I tend to use a C-like notation to express this, I am NOT thinking in terms of C.

Or, of you will - imagine that everything has been cast to the appropriate unsigned width. Since C defines unsigned as
modulo arithmetic, that should not be subject to compiler transformations that make signed overflows undefined.





E.g. the classic unsigned overflow check is (a+b)<a.

Whereas, if I understand things correctly a signed + unsigned overflow check like the below is not guaranteed to work in
the C standard

int16_t a;
uint8_t b;
if( (a+b)<a ) {
overflow
}
a += b;

cannot overflow - the compiler is allowed to remove (a+b)<a, because a+b is computed in signed int16_t precision, and
signed overflow is undefined, so that compiler can assume that the if statement is never true.


Whereas I *think* (and I am sure people will correct me if I am wrong)


int16_t a;
uint8_t b;
if( (int16_t)((uint16_t)a+(uint_16_t)b)<a ) {
overflow
}
a += b;

may work - because (unint16_t)a + (uint16_t)b is an unsigned intermediate, and so is defined tio be modulo arithmetic.

I'm not sure that casting back to signed int16_t will work, but I would be surprised if it did not.



Anyway - I am interested in such code for overflow detection, that does not broaden precision, because broadening is not
always possible.

Optional points if it is C standard compliant.

But standards compliance is not really a requirement, just a nice to have. I'm mainly interested in C-like code that
detects the overflow.




And, I emphasize: I am not interested in this as a practical means of overflow detection. I advocate hardware overflow
detection, whether throwing an exception, setting a flag, or saturating (or several at once).

I am just interested in idioms that might be expressed as a C macro or a C++ inline function, that a compiler might use
to recognize programmer intent, and then generate a more efficient hardware overflow detection code.

I must admit that I am also interested in whether such macros or inline functions could be made elegant enough to be
used in common C or C++ programs. Or other languages.
From: Andy 'Krazy' Glew on
On 6/26/2010 10:40 AM, EricP wrote:
> Andy 'Krazy' Glew wrote:
>>
>> Some examples:
>>
>
> You are really doing signed 9 bit arithmetic there,
> then casting the s9 result back to either a u8 or s8 type.
> Whether there is an overflow or not depends on the result
> type and the value.
>
> e.g.
>
> 0_1010_0101 => u8 = 1010_0101 (ok)
> 0_1010_0101 => s8 = 1010_0101 (signed overflow, sign changed)
>
> (Bits are named b8...b0).
> The unsigned cast overflows if bit_8 is 1,
> whereas the signed cast overflows if bit_8 != bit_7.
>
> u8_result = u8_a + s8_b;
> bit_8 = (u8_result < u8_a);
> if (result_type == s8)
> bit_7 = u8_result < 0;
> overflow = bit_8 != bit_7;
> else
> overflow = bit_8;
> endif
>
> Eric
>
>
>


By the way, one of the common ways of doing a SIMD integer adder is to extend all 8-bit bytes to 9 bits (inserting
zeroes betweebn SIMD boundaries, replicating the previous bit if not), performing the add (as packed 9, 18, 27, 36, 72
bits), detecting overflow at the SIMD boundaries according to whatever types are desired, MUXing in saturation, and then
dropping every 9th bit.
From: Chris Gray on
Andrew Reilly <areilly---(a)bigpond.net.au> writes:

> In my book, using signed int where it is not necessary/appropriate
> *creates* whole classes of bugs, but I'm not fanatical about it. I know
> that there are several worthwhile languages that simply don't have built-
> in types for unsigned integers, so it seems likely that you can get away
> without them...

I agree with the first part. When working on co-operative distributed code,
we often had situations where we were waiting for responses from all nodes.
Rather than having an array of booleans saying who we had heard from,
we used a count of expected responses. If that counter ever went negative,
we had a timing/race bug of some kind, and wanted to know about it. We put
lots of asserts in.

One of the things that using "unsigned" gives you is the ability to tell
the compiler/system that it is an error to try to decrement (or have a
subtract result) below 0. To me, this is equivalent to overflow detection.

With signed values, it is very tempting for folks in the last couple of
generations of programmers to want to use small negative values as special
flag values. If those flag values make it into places where they are not
expected, incorrect execution can silently result. I use unsigned values
where at all possible.

--
Experience should guide us, not rule us.

Chris Gray cg(a)GraySage.COM
From: Andy 'Krazy' Glew on
On 6/26/2010 1:36 PM, Chris Gray wrote:
> Andrew Reilly<areilly---(a)bigpond.net.au> writes:
>
>> In my book, using signed int where it is not necessary/appropriate
>> *creates* whole classes of bugs, but I'm not fanatical about it. I know
>> that there are several worthwhile languages that simply don't have built-
>> in types for unsigned integers, so it seems likely that you can get away
>> without them...
>
> I agree with the first part. When working on co-operative distributed code,
> we often had situations where we were waiting for responses from all nodes.
> Rather than having an array of booleans saying who we had heard from,
> we used a count of expected responses. If that counter ever went negative,
> we had a timing/race bug of some kind, and wanted to know about it. We put
> lots of asserts in.

Note that the code you descrbe does NOT simply work with unsigneds in C, whereas it works with signed.

I.e. you cannot simply say

unsigned response_count;
response_count++;
assert( response_count > 0 );

since C defines wraparound arithmetic for unsigneds, and does not do overflow. (Again, I may be misreading, I don't
have my copy of the C standard (where'd I put it?), and I am sure that i will be told.)

you must do assert(response_count < some_max_count)
and assume that underlow wraps to a large number.


> One of the things that using "unsigned" gives you is the ability to tell
> the compiler/system that it is an error to try to decrement (or have a
> subtract result) below 0. To me, this is equivalent to overflow detection.

Agreed. It wouyld be nice to have the system tell you are trying to make an unsigned number negative.

Note, however, that the C standard defines this, saying that it is modulo arithmetic. Or maybe they only define modulo
for positive numbers. Somebody'll tell me. In any case, C does not give you an error if you try to make an unsigned
negative, except in the simplest cases.

In general, specifying ranges for integers is a good idea. Remember

var a 32..63 ?


From: MitchAlsup on
On Jun 26, 3:36 pm, Chris Gray <c...(a)GraySage.com> wrote:
> One of the things that using "unsigned" gives you is the ability to tell
> the compiler/system that it is an error to try to decrement (or have a
> subtract result) below 0. To me, this is equivalent to overflow detection..

It is BETTER than overflow detection (for detecting array access
problems). And importantly, no integer overflow/underflow detection is
going to catch this one--especially if people continue to use signed
integers for variables that should never contain negative values. Here
is where bounds checking is important and has to be placed there by
the actual software instruction stream.

> With signed values, it is very tempting for folks in the last couple of
> generations of programmers to want to use small negative values as special
> flag values. If those flag values make it into places where they are not
> expected, incorrect execution can silently result. I use unsigned values
> where at all possible.

I only use signed variables when I know of a case where the variable
must contain a negative value some point in its life.

Mitch