Circular Buffer - Find distance between head and Tail

Problem is to find distance between head and tail in a circular buffer, where head is always ahead of tail. But at any point, head or tail may roll over to 0^th location.

Assume that we are rolling over after uint8 i.e 255 entries.

Simple case is like this. Head = 10 Tail =4.

Distance = 10- 4 =6

But say Head is at 4 and tail is at 253.

Distance = 4 – 254 = wont work out (head rolled back to zero after 255)

There is a very simple solution to this problem. .

Formula would be:

 

Distance = Head + 2’s complement of tail

e.g.

0000 1010 (10)

+

­1111 1100 (2’s complement of 4)

========================

0000 0110 (6)

Lets take other example

0000 0100 (4)

+

0000 0010 (2st complement of 254)

===========================

0000 0110 (6)