Sliding window and wrap-around
Noob
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
Noob <root@localhost> wrote:
>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
--
:wq
Noob
> Noob wrote:
>
>> 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.
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.
cr88192
"Noob" <root@localhost> wrote in message
news:480f0d58$0$5410$426a...@news.free.fr...
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...
> Regards.
Richard Tobin
Noob <root@localhost> wrote:
>Implementation-defined means it is documented somewhere, right?
>But where? In the compiler's documentation?
Yes, in theory.
>> 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?
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
--
:wq
Ed Prochak
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
> Noob wrote:
>
>> 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 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
> Noob wrote:
>
>> Implementation-defined means it is documented somewhere, right?
>> But where? In the compiler's documentation?
>
> Yes, in theory.
OK. I'll scour the documentation.
> 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!
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.