Timer, t1-t0, integral promotion

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.

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.

For Addition, it says:

Noncompliant Code Example

unsigned int ui1, ui2, usum;

/* Initialize ui1 and ui2 */

usum = ui1 + ui2;

Compliant Solution (Pre-Condition Test)

unsigned int ui1, ui2, usum;

/* Initialize ui1 and ui2 */

if (UINT_MAX - ui1 < ui2) {
  /* handle error condition */
}
else {
  usum = ui1 + ui2;
}

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

UINT_MAX - ui1 == ui1 ^ UINT_MAX ==> b ^ 0xFFFFFFFF

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

For Subtraction, it says:

Noncompliant Code Example

unsigned int ui1, ui2, udiff;

/* Initialize ui1 and ui2 */

udiff = ui1 - ui2;

#define LWIP_U32_DIFF(a, b) (((a) >= (b)) ? ((a) - (b)) : (((a) + ((b) ^ 0xFFFFFFFF) + 1)))

When ( a < b ), max_a is (b-1), min_a is 0,
the result == a + (UINT_MAX - b) + 1,
max_result == (b-1) + (UINT_MAX - b) + 1,
min_result == 0 + (UINT_MAX - b) + 1,
no wrapping.

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


void main(void)
{
        uint16_t a16 = 0xFFFF, b16 = 1234, r16;
        uint32_t a32 = 0xFFFF, b32 = 1234, r32;

        r16 = a16 * b16;
        r32 = a32 * b32;
        printf("r16 = %u\n", r16);
        printf("r32 = %u\n", r32);
        printf( "r32 mod 0x10000 = %u\n", ( r32 % 0x10000 ) );

        system("PAUSE");
}

r16 = 64302
r32 = 80870190
r32 mod 0x10000 = 64302

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


void main(void)
{
        int16_t a16 = 32760, b16 = 1234, r16, r16_chk = -9872;
        int32_t a32 = 32760, b32 = 1234, r32;

        r16 = a16 * b16;
        r32 = a32 * b32;
        printf("r16 = %d\n", r16);
        printf("r32 = %d\n", r32);
        printf( "r32 mod 0x10000 = %d\n", ( r32 % 0x10000 ) );
        printf( "r16_chk = %u\n", (uint16_t)r16_chk );

        system("PAUSE");
}

r16 = -9872
r32 = 40425840
r32 mod 0x10000 = 55664
r16_chk = 55664

Modular arithmetic

en.wikipedia.org/.../Modular_arithmetic

(It is too difficult for me, so I simply skip it.)

Help me find the place in the standard where it describes the behavior of unsigned integer overflow and underflow during addition and subtraction.

Never mind, I found a satisfactory answer. If anyone is interested, it's here

groups.google.com/.../5975d5d43d33a914

and here

groups.google.com/.../a23d05b62d198a20

Computations that could lead to an overfow include addition and multiplication.

They include those, yes, but they're not limited to those. But they just as well include subtraction, shifts, unary minus. That's why it says "computation", not "addition", nor "addition and multiplication".

Help me find the place in the standard where it describes the behavior of unsigned integer overflow and underflow during addition and subtraction.

But you already found it! It says there is no such thing as overflow on unsigned arithmetic. How much more clear could that possibly be?

Noncompliant Code Example

Careful dragging that into this discussion. Compliance to some rules that have been invented, with no particular relation to the language itself---which that's about---s an entirely different issue than the well-definedness of operations specified by the language itself.

if (UINT_MAX - ui1 < ui2) {
  /* handle error condition */
}

It is by no means clear that this is even is any kind of "error condition". In the case this thread is about it most decidedly would not be.

There is absolutely nothing wrong with a 32-bit timer rolling over from a starting point of, say, 0xFFFFFF80 to 0x00000003. Plain and simple subtraction of those numbers yields exactly the elapsed number of counts: 0x00000083. Look, Ma, no error!