Signed, Unsigned, and Circular

Signed, Unsigned, Circular

In doing networking work and related kernel work, we have seen every new developer run into a variation of a simple problem with the use of counters that wrap around.  In the case of TCP, it is sequence numbers.  In the case of kernel work, it is jiffies.  It also happens when you are waiting for your two digit number to be called in a fast food place.

Suppose that two events happen, named a and b.  The event a happened earlier in real time than b happened.  Records of these events are stamped with a limited resolution timer, and upper bits that tell you the true ordering are discarded.  To make the problem easier to reason about, we will use an 8-bit timer.

struct Event { uint8 sequenceNumber; .... }

We are assuming a 2s compliment representation of integers; the standard computer integer representation.  So, should these timestamps really be signed or unsigned values?  They are usually implemented using unsigned values, but they are actually neither.  People get bugs in their code by asking if one event happened before another by comparing sequenceNumber using the less than operator, which is wrong.  We are assuming a 2s compliment representation of integers; the standard computer integer representation.  So, should these timestamps really be signed or unsigned values?

Geometry Of Circular Numbers

Firstly, 2s compliment numbers are circular in some sense just by virtue of their limited number of bits.  For all of them, addition and multiplication work in the same way.  But whether a number is signed, unsigned, or circular depends on: the definition of bit extension when assigning to a larger number of bits, the definition of the comparators, and the definition of whether some arithmetic overflowed.  Beware of ignoring these distinctions!

Assume that events are stamped around a clock going clockwise.  Event a is defined to be less than b when a diameter (a,a') contains b in the arc clockwise to it.  In this graphic, the diameter(b,b') contains a only in the counterclockwise arc, so b is greater than a.  This is the same thing as saying that the distance between from a to b is positive (as a signed integer).

The comparison is only valid if the real distance (including the lost upper bits in the sequence number) between a and b is half of the total distance around the circle.  Also, circular numbers cannot really be extended (ie: assigned to a value with more bits) without  invalidating ordering relationships of the original values.

Because they can't really be sign extended (without changing their values), and have their own comparison operators, they really should have their own type.  (Don't get me started about network versus host ordered ints not being native!)

circular int8 sequenceNumber;

In the Linux kernel headers, jiffies.h explicitly states that it initializes the jiffies counter on bootup to be negative 5 minutes into the past so that the kernel will crash 5 minutes after startup if you treat jiffies like unsigned integers.

Circular numbers are in use when you see macros that redefine comparison like:  "((signed)b - (signed)a) > 0", where b and a are usually unsigned storage types.

Geometry of Unsigned and Unsigned Numbers

The point a is considered (signed) less than b if clockwise along the arc from the maximum negative number m, we first encounter a.  Signed values are extended by copying the higest bit (a sign bit) into the new bytes; ie: extend negative numbers with 1s and positives with 0s.

The point b is considered (unsigned) less than a if clockwise along the arc from z we first encounter b.  They are extended by padding with 0s.