Response from Stian Skjelstad on mailinglist:

Looking at Hiromasa ITO numbers:

if (TCP_SEQ_BETWEEN(pcb->rcv_nxt, seqno + 1, seqno + tcplen - 1)) {
                      u32         u32         u32       u16

seqno + 1          : 0x13d897cb
seqno + tcplen - 1 : 0x13d897ca /* this is smaller than seqno + 1, so already here, we see that this test should currently ALWAYS fail, when viewed with human eyes. It should be impossible to fit a number within the given range*/
pcb->rcv_nxt       : 0x93d897ca

TCP_SEQ_GEQ(0x93d897ca, 0x13d897cb) && TCP_SEQ_LEQ (0x93d897ca, 0x13d897ca)

/* signed compare*/      /* signed compare*/
  (0x7FFFFFFF >= 0)   && ( 0x80000000 <= 0)
  (2147483647 >= 0)   && (-2147483648 <= 0)


It looks like we should inspect tcplen before checking TCP_SEQ_BETWEEN. Currently tcplen is checked for greater than zero, but it should be greater than 1 for the current test to be valid (parameter 3 should be same size or greater than 2)

Reopen bug so this does not get lost

@Simon, all can be expressed in terms of LT as I have shown in the first post. Here is passing test code showing my macros behave the same as current ones in edge cases (a=b-1, a=b, a=b+1).



#include <assert.h>
#include <stdint.h>

typedef uint32_t u32_t;
typedef int32_t s32_t;

#define TCP_SEQ_LT(a,b) ((u32_t)((u32_t)(a) - (u32_t)(b)) >= 0x80000000u)
#define TCP_SEQ_LEQ(a,b) (!(TCP_SEQ_LT(b,a)))
#define TCP_SEQ_GT(a,b) TCP_SEQ_LT(b,a)
#define TCP_SEQ_GEQ(a,b) TCP_SEQ_LEQ(b,a)

#define TCP_SEQ_LT_OLD(a,b)     ((s32_t)((u32_t)(a) - (u32_t)(b)) < 0)
#define TCP_SEQ_LEQ_OLD(a,b)    ((s32_t)((u32_t)(a) - (u32_t)(b)) <= 0)
#define TCP_SEQ_GT_OLD(a,b)     ((s32_t)((u32_t)(a) - (u32_t)(b)) > 0)
#define TCP_SEQ_GEQ_OLD(a,b)    ((s32_t)((u32_t)(a) - (u32_t)(b)) >= 0)

int main()
{
    assert(TCP_SEQ_LT    (5, 6));
    assert(TCP_SEQ_LT_OLD(5, 6));
   
    assert(!TCP_SEQ_LT    (6, 6));
    assert(!TCP_SEQ_LT_OLD(6, 6));
   
    assert(!TCP_SEQ_LT    (7, 6));
    assert(!TCP_SEQ_LT_OLD(7, 6));
   
   
    assert(TCP_SEQ_LEQ    (5, 6));
    assert(TCP_SEQ_LEQ_OLD(5, 6));
   
    assert(TCP_SEQ_LEQ    (6, 6));
    assert(TCP_SEQ_LEQ_OLD(6, 6));
   
    assert(!TCP_SEQ_LEQ    (7, 6));
    assert(!TCP_SEQ_LEQ_OLD(7, 6));
   
   
    assert(!TCP_SEQ_GT    (5, 6));
    assert(!TCP_SEQ_GT_OLD(5, 6));
   
    assert(!TCP_SEQ_GT    (6, 6));
    assert(!TCP_SEQ_GT_OLD(6, 6));
   
    assert(TCP_SEQ_GT    (7, 6));
    assert(TCP_SEQ_GT_OLD(7, 6));
   
   
    assert(!TCP_SEQ_GEQ    (5, 6));
    assert(!TCP_SEQ_GEQ_OLD(5, 6));
   
    assert(TCP_SEQ_GEQ    (6, 6));
    assert(TCP_SEQ_GEQ_OLD(6, 6));
   
    assert(TCP_SEQ_GEQ    (7, 6));
    assert(TCP_SEQ_GEQ_OLD(7, 6));
   
   
    // Sanity check asserts are enabled
    assert(0);
   
    return 0;
}

For these cases, the subject can be changed after creation.

@abizjak - If you want to start nit-picking, you may at least try to be careful about your own wording.  Your summary claims "undefined behavior", but then you quote the relevant part of the standard that says "implementation-defined behavior".

So, basically you complain that lwip assumes 2-complement.

@mywave - converting -1 to u32_t is done by repeatedly adding ("mathematically") UINT32_MAX+1, so (after just one iteration) you will get the expected 0xffffffff

C99 standard says this:

------
6.3.1.3 Signed and unsigned integers

1 When a value with integer type is converted to another integer type other than _Bool, if
the value can be represented by the new type, it is unchanged.

2 Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or
subtracting one more than the maximum value that can be represented in the new type
until the value is in the range of the new type.49)

3 Otherwise, the new type is signed and the value cannot be represented in it; either the
result is implementation-defined or an implementation-defined signal is raised.
------

In other words, converting any integer type to some unsigned integer type is always safe (modulo reduction), but converting to a signed integer type is not. It is not literally undefined behavior but still not something one should rely on.

I'm not saying the current macro gives incorrect results just that it invokes implementation-defined behavior according to the C standard. I think its behavior is perfectly sane otherwise (and equivalent to the solutions I gave).

Consider the case where a is 0xFFFFFFFF and b is 0. Then ((u32_t)(a)-(u32_t)(b)) has value 0xFFFFFFFF (and type u32_t or something wider that can represent any u32_t in case of promotions). Then, (s32_t)((u32_t)(a)-(u32_t)(b)) invokes implementation-defined behavior because 0xFFFFFFFF cannot be represented in s32_t.

typecasting between s32_t and u32_t is not undefined behaviour. On (almost all) systems, CPU work in 2nd compliments and the only differences about u32_t and s32_t are which branch instructions or which comparison instruction to use.

The only situations where unwanted results might occur is when going from 16bit into 32bit. Example: u16_t into s32_t will cause numbers to not be signed extended (-1 will become 0x0000ffff for example).

The current macro will for example detect sequence number 0x00000004 to come after 0xfffffffe, since it only looks at the delta, ignoring that it has wrapped around zero.


In which situation does the current macro fail to give the correct result?



(file #41185)

See TCP_SEQ_LT and similar macros:
http://git.savannah.gnu.org/cgit/lwip.git/tree/src/include/lwip/priv/tcp_priv.h#n106

Two u32 are subtracted and the result is converted to s32. This is undefined behavior when the value is not representable in s32.

Fixed code:

#define TCP_SEQ_LT(a,b)     (((u32_t)(a) - (u32_t)(b)) >= 0x80000000u)
or
#define TCP_SEQ_LT(a,b)     ((((u32_t)(a) - (u32_t)(b)) & 0x80000000u) != 0)
or
#define TCP_SEQ_LT(a,b)     (((u32_t)(a) - (u32_t)(b)) >> 31)

In other words, a is less then b when the most significant bit in (a - b) mod 2^32 is set. One can see how this is exactly the same as the current implementation except for the the lack of undefined behavior, considering twos complement difference is the same thing as unsigned difference bitwise, and the sign bit is the most significant bit.

And the others can be expressed in terms of this one:

#define TCP_SEQ_LEQ(a,b)    (!(TCP_SEQ_LT(b,a)))
#define TCP_SEQ_GT(a,b)     TCP_SEQ_LT(b,a)
#define TCP_SEQ_GEQ(a,b)    TCP_SEQ_LEQ(b,a)

This is a theoretical bug, I chose "Crash Error" since it can in theory cause a crash.