Timer, t1-t0, integral promotion

Does the below code still work?

void delay(uint32_t delay)
{
    int32_t t0;
    t0 = (int32_t)TIMER_VALUE; /* assuming the timer is 32-bit */
    while ( ( (int32_t)TIMER_VALUE - t0 ) < delay );
}

signed arithmetic overflows cleanly

Does the below code still work?

void delay(uint32_t delay)
{
    int32_t t0;
    t0 = (int32_t)TIMER_VALUE; /* assuming the timer is 32-bit */
    while ( ( (int32_t)TIMER_VALUE - t0 ) < delay );
}

signed arithmetic overflows cleanly

I am using my stupid way to try to figure out the key point.

#include <stdio.h>
#include <stdint.h>


void main(void)
{
        int32_t now = -2147483648, end;
        end = now - 1;
        // while (now - end < 0);
        printf("now = %d\n", now);
        printf("end = %d\n", end);

        if ( (int32_t)(now - end) < 0 )
                printf("Less than 0\n");
        else
                printf("It is >= Zero\n");

        system("PAUSE");
}

now = -2147483648
end = 2147483647
It is >= Zero

#include <stdio.h>
#include <stdint.h>


void main(void)
{
        int32_t now = -2147483648, end;
        end = now - 1;
        // while (now - end < 0);
        printf("now = %d\n", now);
        printf("end = %d\n", end);

        if ( (now - end) < 0 )
                printf("Less than 0\n");
        else
                printf("It is >= Zero\n");

        system("PAUSE");
}

now = -2147483648
end = 2147483647
It is >= Zero

It is the same.

#include <stdio.h>
#include <stdint.h>


void main(void)
{
        int16_t now = -32768, end;
        end = now - 1;
        // while (now - end < 0);
        printf("now = %d\n", now);
        printf("end = %d\n", end);

        if ( (int16_t)(now - end) < 0 )
                printf("Less than 0\n");
        else
                printf("It is >= Zero\n");

        system("PAUSE");
}

now = -32768
end = 32767
It is >= Zero

#include <stdio.h>
#include <stdint.h>


void main(void)
{
        int16_t now = -32768, end;
        end = now - 1;
        // while (now - end < 0);
        printf("now = %d\n", now);
        printf("end = %d\n", end);

        if ( (now - end) < 0 )
                printf("Less than 0\n");
        else
                printf("It is >= Zero\n");

        system("PAUSE");
}

now = -32768
end = 32767
Less than 0

It is different.

Does the below code still work?

As far as I can see, it should. There are some subtle points in this code.
1) TIMER_VALUE is converted from uint32_t to int32_t. We are assuming two's complement arithmetic.
2) Two values of type int32_t are subtracted with (likely) an overflow. Again, we are assuming two's complement arithmetic, so the result really is the number of ticks elapsed.
3) According to integer promotion rules, the result of subtraction is converted to uint32_t prior to comparison. That doesn't change anything since we know that the result is positive anyway.

I wonder if the same can be done with fewer type conversions:

void delay(uint32_t delay)
{
    uint32_t t0;
    t0 = TIMER_VALUE; /* assuming the timer is 32-bit */
    while ( ( TIMER_VALUE - t0 ) < delay );
}

Since we are assuming two's complement arithmetic anyway, we might as well get rid of conversion to signed integer. So points 1) and 3) above no longer apply. Going to signed integer was plain stupidity on my part, I suppose.

By the way, here is how lwip computes the difference between two timer values:

/** Get the absolute difference between 2 u32_t values (correcting overflows)
 * 'a' is expected to be 'higher' (without overflow) than 'b'. */
#define LWIP_U32_DIFF(a, b) (((a) >= (b)) ? ((a) - (b)) : (((a) + ((b) ^ 0xFFFFFFFF) + 1)))

I beleive this code does not depend on two's complement arithmetic and it avoids subtraction with overflow. A smart compiler should simply replace the macro with ((a) - (b)) where it is safe to do so.

It is different.

No wonder.
When you are doing ( (now - end) < 0 ), the 16-bit signed integers are promoted to 32-bit ones prior to subtraction, so an overflow is no longer possible. Hence, the result is negative.
When you are doing ( (int16_t)(now - end) < 0 ), you are converting the result of subtruction (which is -65535 or 0xFFFF0001) to int16_t. The conversion simply throws away the upper 16 bits, so you are left with 0x0001 which is positive.

@John Linq,

You are _not_ stupid and you are certainly _not_ an idiot !

#include <stdio.h>
#include <stdint.h>


void main(void)
{
        uint32_t t0 = 4294967290, t1 = 19;    // t1 < t0

        printf("t0 u = %u\n", t0);
        printf("t1 u = %u\n", t1);
        printf("t0 d = %d\n", t0);
        printf("t1 d = %d\n", t1);

        printf("result u = %u\n", (t1 - t0));
        printf("result d = %d\n", (t1 - t0));

        if ( (t1 - t0) == 25 )
                printf("OK\n");
        else
                printf("NG\n");

        system("PAUSE");
}

t0 u = 4294967290
t1 u = 19
t0 d = -6
t1 d = 19
result u = 25
result d = 25
OK

#include <stdio.h>
#include <stdint.h>


void main(void)
{
        int32_t t0 = 2147483640, t1 = -2147483631;    // t1 < t0

        printf("t0 u = %u\n", t0);
        printf("t1 u = %u\n", t1);
        printf("t0 d = %d\n", t0);
        printf("t1 d = %d\n", t1);

        printf("result u = %u\n", (t1 - t0));
        printf("result d = %d\n", (t1 - t0));

        if ( (t1 - t0) == 25 )
                printf("OK\n");
        else
                printf("NG\n");

        system("PAUSE");
}

t0 u = 2147483640
t1 u = 2147483665
t0 d = 2147483640
t1 d = -2147483631
result u = 25
result d = 25
OK

For int32_t/uint32_t, the result is what I want.
Due to the integral promotion, the result of int16_t/uint16_t is not I want.

My mistake:

#include <stdio.h>
#include <stdint.h>


void main(void)
{
        int32_t t0 = 2147483640, t1 = 123;    // t1 < t0

        printf("t0 u = %u\n", t0);
        printf("t1 u = %u\n", t1);
        printf("t0 d = %d\n", t0);
        printf("t1 d = %d\n", t1);

        printf("result u = %u\n", (t1 - t0));
        printf("result d = %d\n", (t1 - t0));

        system("PAUSE");
}

t0 u = 2147483640
t1 u = 123
t0 d = 2147483640
t1 d = 123
result u = 2147483779
result d = -2147483517

#include <stdio.h>
#include <stdint.h>


void main(void)
{
        uint32_t t0 = 2147483640, t1 = 123;    // t1 < t0

        printf("t0 u = %u\n", t0);
        printf("t1 u = %u\n", t1);
        printf("t0 d = %d\n", t0);
        printf("t1 d = %d\n", t1);

        printf("result u = %u\n", (t1 - t0));
        printf("result d = %d\n", (t1 - t0));

        system("PAUSE");
}

t0 u = 2147483640
t1 u = 123
t0 d = 2147483640
t1 d = 123
result u = 2147483779
result d = -2147483517

My mistake again:

#include <stdio.h>
#include <stdint.h>


void main(void)
{
        int32_t t0 = 2147483640, t1 = 123;    // t1 < t0

        printf("t0 u = %u\n", t0);
        printf("t1 u = %u\n", t1);
        printf("t0 d = %d\n", t0);
        printf("t1 d = %d\n", t1);

        printf("result u = %u\n", (t1 - t0));
        printf("result d = %d\n", (t1 - t0));

        if ( (t1 - t0) == 2147483779 )
            printf("OK\n");
        else
            printf("NG\n");

        system("PAUSE");
}

t0 u = 2147483640
t1 u = 123
t0 d = 2147483640
t1 d = 123
result u = 2147483779
result d = -2147483517
OK

It is still OK!!!

I think this topic is too difficult to understand for me.

Many thanks to everyone involved.

My favorite:

/* both t0 and timer_val are unsigned */
t0 = timer_val;
while ( (cast to timer-size unsigned)( timer_val - t0 ) < delay_val );

By the way, here is how lwip computes the difference between two timer values:

/** Get the absolute difference between 2 u32_t values (correcting overflows)
 * 'a' is expected to be 'higher' (without overflow) than 'b'. */
#define LWIP_U32_DIFF(a, b) (((a) >= (b)) ? ((a) - (b)) : (((a) + ((b) ^ 0xFFFFFFFF) + 1)))

That macro is a spectacular waste of effort, based on the completely false assumption that unsigned arithmetic had any overflows that would need "correcting". Oh, and the comment is wrong, too: that macro computes the difference, not the absolute difference. The latter would be something like (a >= b)?(a - b):(b - a)

So let's dig in:

b & 0xFFFFFFFF

is exactly equivalent to

0xFFFFFFFF - b

which makes the term to the right of the ':' operator:

a + (0xFFFFFFFF - b) + 1

which in term is exactly the same as:

a - b + (0x100000000)

but since we're assuming 32-bit unsigned integers, which wrap around modulo 0x100000000, that's nothing else but

a - b

There are three cases you can end up in if you use this:

1) it's identical to a much simpler

#define LWIP_U32_DIFF(a,b) ((a)-(b))

2) u32_t is not actually a 32-bit integer type. In that case the macro doesn't work any better than the simpler version from case 1) would.

3) something happens that you pretty definitely didn't want to. Imagine what will happen if you call this as LWIP_U32_DIFF(a++, TIMER_REGISTER), and see what multiple evaluation of those arguments will do your result.

that's nothing else but (a - b)

My understanding is that the author is trying to avoid subtracting unsigned integers with an overflow (or is it underfow?) If you can point me to the exact place in the C standard where it describes the behavior of unsigned integer underflow, I would be grateful. All I could find is this:

A computation involving unsigned operands can never overlow,
because a result that cannot be represented by the resulting unsigned integer type is
reduced modulo the number that is one greater than the largest value that can be
represented by the resulting type.

As far as I understand this, it applies to addition. I'm not so sure about subtraction. But English is not my first language, maybe I'm missing something?

As far as I understand this, it applies to addition.

I have no idea how you could possibly have arrived at that understanding. Addition isn't even mentioned in that excerpt from the standard, nor was it taken from the section about the '+' operator: it's from C99 6.2.5 "Types", paragraph 9. Do you really think the Standard authors would have written "A computation" if they had meant "An addition"?

Do you really think the Standard authors would have written "A computation" if they had meant "An addition"?

Yes, I do. Computations that could lead to an overfow include addition and multiplication.
Please stop being so negative for a minute. Help me find the place in the standard where it describes the behavior of unsigned integer overflow and underflow during addition and subtraction.

Just try to provide some information (may be useless), sorry for any of my improper behaviors.

===================================================================

www.securecoding.cert.org/.../INT30-C. Ensure that unsigned integer operations do not wrap

INT30-C. Ensure that unsigned integer operations do not wrap

According to C99, Section 6.2.5, "Types"

A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

This behavior is more informally referred to as unsigned integer wrapping. Unsigned integer operations can wrap if the resulting value cannot be represented by the underlying representation of the integer. The following table indicates which operators can result in wrapping:

[skip]

Subtraction

Subtraction is between two operands of arithmetic type, two pointers to qualified or unqualified versions of compatible object types, or between a pointer to an object type and an integer type. See rules ARR36-C. Do not subtract or compare two pointers that do not refer to the same array, ARR37-C. Do not add or subtract an integer to a pointer to a non-array object, and ARR38-C. Do not add or subtract an integer to a pointer if the resulting value does not refer to a valid array element for information about pointer subtraction. Decrementing is equivalent to subtracting one.