Sliding window and wrap-around

[Noob]

Hello,

Consider the following scenario.
'A' produces data which are sent in "packets" to 'B'.
Each "packet" carries a sequence number, so that 'B' can
insert the packet in the "right place" in a sorted list.

The sequence number of the 1st packet is 0.
The sequence number of the 65536th packet is 65535.
The sequence number of the 65537th packet "wraps around" back to 0.

Because of the wrap-around, I can't just use the normal relational
operators. For example, with very high probability, seqno 0 is newer
than seqno 65535, which translates to : 0 "is greater than" 65535.

Given a sequence number 'u'
u+1, u+2, ..., u+32767 (mod 65536) are considered greater than u.
u-1, u-2, ..., u-32768 (mod 65536) are considered lower than u.

I have implemented this as :

#include <stdint.h>
int greater_than(uint16_t u, uint16_t v)
{
return (int16_t)(u-v) > 0;
}

This works on my platform (GCC, Linux, x86) but AFAIU, conversion
from unsigned to signed integer is undefined?

Is there a way to implement the comparison function in a
portable manner?

Regards.

 

[Richard Tobin]

Given a sequence number 'u'
u+1, u+2, ..., u+32767 (mod 65536) are considered greater than u.
u-1, u-2, ..., u-32768 (mod 65536) are considered lower than u.

I have implemented this as :

#include <stdint.h>
int greater_than(uint16_t u, uint16_t v)
{
return (int16_t)(u-v) > 0;
}

This works on my platform (GCC, Linux, x86) but AFAIU, conversion
from unsigned to signed integer is undefined?

Yes, or rather implementation-defined.

The unsigned arithmetic is defined to work mod 65536, so I suggest

return (u - v) <= 32767;

-- Richard

 

[cr88192]

Hello,

Consider the following scenario.
'A' produces data which are sent in "packets" to 'B'.
Each "packet" carries a sequence number, so that 'B' can
insert the packet in the "right place" in a sorted list.

The sequence number of the 1st packet is 0.
The sequence number of the 65536th packet is 65535.
The sequence number of the 65537th packet "wraps around" back to 0.

Because of the wrap-around, I can't just use the normal relational
operators. For example, with very high probability, seqno 0 is newer
than seqno 65535, which translates to : 0 "is greater than" 65535.

Given a sequence number 'u'
u+1, u+2, ..., u+32767 (mod 65536) are considered greater than u.
u-1, u-2, ..., u-32768 (mod 65536) are considered lower than u.

I have implemented this as :

#include <stdint.h>
int greater_than(uint16_t u, uint16_t v)
{
return (int16_t)(u-v) > 0;
}

This works on my platform (GCC, Linux, x86) but AFAIU, conversion
from unsigned to signed integer is undefined?

Is there a way to implement the comparison function in a
portable manner?

that will not work right in general...


what you would need to do instead is to keep track of the rover, and so, for
example:
if(u<rov)u+=65536;
if(v<rov)v+=65536;
return(u>v);

note that all this works so long as one does not do absolute comparrisons,
or retains sequence numbers out of range of the window.

or such...

 

[Noob]

Yes, or rather implementation-defined.

Right. The standard states

<quote>
When an unsigned integer is converted to its corresponding
signed integer, if the value cannot be represented the result
is implementation-defined.
</quote>

Implementation-defined means it is documented somewhere, right?
But where? In the compiler's documentation?

(e.g. GCC runs on many platforms; would the documentation have
to specify the behavior for every supported architecture?)

The unsigned arithmetic is defined to work mod 65536, so I suggest

return (u - v) <= 32767;

Are u and v of type uint16_t in this expression?
What if stdint.h is not available?

If uint16_t is a typedef for unsigned short, aren't u and v
promoted to int before performing the subtraction?

Is there a solution using only unsigned or unsigned long,
without assuming any specific width for these types?

Regards.

 

[Richard Tobin]

Implementation-defined means it is documented somewhere, right?
But where? In the compiler's documentation?

Yes, in theory.

Are u and v of type uint16_t in this expression?
Yes.

What if stdint.h is not available?

Then it won't compile.

If uint16_t is a typedef for unsigned short, aren't u and v
promoted to int before performing the subtraction?

Yes, I should have said

return (uint16_t)(u - v) <= 32767;

Is there a solution using only unsigned or unsigned long,
without assuming any specific width for these types?

The OP's problem assumed the existence of uint16_t. You could operate
on unsigned and reduce the result mod 65536 if you thought it might
not be available. But the fact that the sequence numbers wrap around
at 65536 strongly suggests that 16-bit integers are available!

-- Richard

 

[Ed Prochak]

Hello,

Consider the following scenario.
'A' produces data which are sent in "packets" to 'B'.
Each "packet" carries a sequence number, so that 'B' can
insert the packet in the "right place" in a sorted list.

The sequence number of the 1st packet is 0.
The sequence number of the 65536th packet is 65535.
The sequence number of the 65537th packet "wraps around" back to 0.

Because of the wrap-around, I can't just use the normal relational
operators. For example, with very high probability, seqno 0 is newer
than seqno 65535, which translates to : 0 "is greater than" 65535.

Given a sequence number 'u'
u+1, u+2, ..., u+32767 (mod 65536) are considered greater than u.
u-1, u-2, ..., u-32768 (mod 65536) are considered lower than u.

I have implemented this as :

#include <stdint.h>
int greater_than(uint16_t u, uint16_t v)
{
return (int16_t)(u-v) > 0;

}

This works on my platform (GCC, Linux, x86) but AFAIU, conversion
from unsigned to signed integer is undefined?

Is there a way to implement the comparison function in a
portable manner?

Regards.

Outside the C types question, It isn't clear to me what the problem
is. Do you really expect to get >65535 packets? You do not have any
other way of knowing the difference between packet #00000 and #65536.
So on the receiving end you must have already gotten packet #00000.
Can you not simply try to insert in the list and seeing the collision,
you determine if this is a duplicate of packet #00000 or a new packet
#65536. This is less a C question in my mind than a hash collision
algorithm question.

Does that help?
Ed

 

[Noob]

that will not work right in general...

What will not work in general?

what you would need to do instead is to keep track of the rover,
and so, for example:
if(u<rov)u+=65536;
if(v<rov)v+=65536;
return(u>v);

What are rover and rov?
Could you detail the algorithm?

note that all this works so long as one does not do absolute comparisons,

What do you consider an absolute comparison?

or retains sequence numbers out of range of the window.

or such...

Or such?

 

[Noob]

Outside the C types question, It isn't clear to me what the problem
is. Do you really expect to get >65535 packets?

Yes.

'A' sends between 100 and 5000 packets per second.

Therefore, wrap-around might occur as often as every 13 seconds.

You do not have any
other way of knowing the difference between packet #00000 and #65536.

(Is it a question?) No, I have no way to tell apart two packets with
the same sequence number; they might be the same (duplicated) packet,
or they might be different packets, the sequence numbers of which are
spaced 65536*k apart.

So on the receiving end you must have already gotten packet #00000.
Can you not simply try to insert in the list and seeing the collision,

I don't keep the packets forever, they are sent "downstream".

you determine if this is a duplicate of packet #00000 or a new packet
#65536. This is less a C question in my mind than a hash collision
algorithm question.

Does that help?

I'll think about it.

Regards.

 

[Noob]

Yes, in theory.

OK. I'll scour the documentation.

Yes, I should have said

return (uint16_t)(u - v) <= 32767;


The OP's problem assumed the existence of uint16_t. You could operate
on unsigned and reduce the result mod 65536 if you thought it might
not be available. But the fact that the sequence numbers wrap around
at 65536 strongly suggests that 16-bit integers are available!

It is the protocol that mandates storing sequence numbers in
a 16-bit wide field. This protocol might be implemented on
platforms that do not provide exact width integers.

As far as I can tell, the original implementation...

#include <stdint.h>
int greater_than(uint16_t u, uint16_t v)
{
return (int16_t)(u-v) > 0;
}

is equivalent to...

int greater_than2(unsigned long u, unsigned long v)
{
return ((u-v-1UL) & 0xffffUL) < 0x7fffUL;
}

The second implementation should (??) be portable to any platform.

Regards.