CODEWITHSUNDEEP
c
user1255770
user1255770

Reputation: 1642

How does unsigned subtraction work when it wraps around?

This is a macro in the lwIP source code:

#define TCP_SEQ_LT(a,b)     ((int32_t)((uint32_t)(a) - (uint32_t)(b)) < 0)

Which is used to check if a TCP sequence number is less than another, taking into account when the sequence numbers wrap around. It exploits the fact that arithmetic wraps around, but I am unable to understand how this works in this particular case.

Can anyone explain what happens and why the above works ?

Upvotes: 6

Views: 7627

Answers (3)

ryanbwork
ryanbwork

Reputation: 2153

Take a simple 4 bit integer example where a = 5 and b = 6. The binary representation of each will be

a = 0101
b = 0110

Now when we subtract these (or take two's complement of b, sum with a, and add 1), we get the following

0101
1001
+  1
-----
1111

1111 is equal to 15 (unsigned) or -1 (signed, again translated using two's complement). By casting the two numbers to unsigned, we ensure that if b > a, the difference between the two is going to be a large unsigned number and have it's highest bit set. When translating this large unsigned number into its signed counterpart we will always get a negative number due to the set MSB.

As nos pointed out, when a sequence number wraps around from the max unsigned value back to the min, the macro will also return that the max value is < min using the above arithmetic, hence its usefulness.

Upvotes: 3

Evo510
Evo510

Reputation: 173

Because it is first cast as a signed integer before it is compared to zero. Remember that the first bit reading from left to right determines the sign in a signed number but is used to increase the unsigned int's range by an extra bit.

Example: let's say you have a 4 bit unsigned number. This would mean 1001 is 17. But as a signed integer this would be -1.

Now lets say we did b0010 - b0100. This ends up with b1110. Unsigned this is 14, and signed this is -6.

Upvotes: 0

Paul Rubel
Paul Rubel

Reputation: 27232

On wrap-around a will be much greater than b. If we subtract them the result will also be very large, ie have its high-order bit set. If we then treat the result as a signed value the large difference will turn into a negative number, less than 0.

If you had 2 sequence numbers 2G apart it wouldn't work, but that's not going to happen.

Upvotes: 0

Related Questions