Velocity Reviews > Array index subtraction and wrapping

# Array index subtraction and wrapping

wearyofallthiscrap@gmail.com
Guest
Posts: n/a

 06-26-2007
(I'm posting this via Google, I apologize if the From: line is
completely
broken.)

I'm trying to track down a bug in some code which handles memory
buffers.
I'm not accustomed to using C, and there's an idiom which is confusing
me.

Calculating the
size is being done with lines like this:

end = (head + (buffer_size - tail)) % buffer_size;
size = end;

Now, I understand (I think) why the math is ordered the way it is, to
avoid any potential integer overflow when "head + buffer_size" would
have
been calculated. What I don't understand is why

would not have been sufficient? What's the point of "wrapping" the
numbers around the buffer, so to speak?

Eric Sosman
Guest
Posts: n/a

 06-26-2007
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote On 06/26/07 17:05,:
> (I'm posting this via Google, I apologize if the From: line is
> completely
> broken.)
>
> I'm trying to track down a bug in some code which handles memory
> buffers.
> I'm not accustomed to using C, and there's an idiom which is confusing
> me.
>
> Calculating the
> size is being done with lines like this:
>
> end = (head + (buffer_size - tail)) % buffer_size;
> size = end;
>
> Now, I understand (I think) why the math is ordered the way it is, to
> avoid any potential integer overflow when "head + buffer_size" would
> have
> been calculated. What I don't understand is why
>
> size = head - tail;
>
> would not have been sufficient? What's the point of "wrapping" the
> numbers around the buffer, so to speak?

For concreteness, let's imagine buffer_size == 100.
To begin, we'll suppose that 90 items have been inserted
in the buffer, so head == 90, and the first 50 of them
is the index where the next inserted item will go and
tail is the index from which the next removed item will
be taken; the actual boundary conventions in your code
may be different.) How many items are still in the
buffer? head - tail == 40, as you suggest.

Now insert 30 more items. The first ten go into
positions [90] through [99], but then what? Probably,
head wraps around to zero and re-uses positions [0]
through [19] for the rest. So now we have head == 20,
tail == 50. How many items are now in the buffer? We
had 40, we added 30 more, so there are now 70. But
what is the value of head - tail? It is -30, which is
a peculiar number of items ...

This arrangement where a pair of array indices or
a pair of pointers chase each other around and around
a fixed-size array but are never allowed to cross is
known as a "circular buffer," by analogy with what
happens as you go around a circle counting degrees
as you go: 357, 358, 359, 0, 1, 2, ... The successor
of the last slot in the array is the first slot. Most
and tail -- but sometimes there may be three or more.
(I've never seen more than four used, but I bet someone
has.)

--
(E-Mail Removed)

CBFalconer
Guest
Posts: n/a

 06-26-2007
(E-Mail Removed) wrote:
>
> (I'm posting this via Google, I apologize if the From: line is
> completely
> broken.)
>
> I'm trying to track down a bug in some code which handles memory
> buffers. I'm not accustomed to using C, and there's an idiom
> which is confusing me.
>
> Calculating the size is being done with lines like this:
>
> end = (head + (buffer_size - tail)) % buffer_size;
> size = end;

size = (tail - end) % buffer_size;
>
> Now, I understand (I think) why the math is ordered the way it is,
> to avoid any potential integer overflow when "head + buffer_size"
> would have been calculated. What I don't understand is why
>
> size = tail - head; /* corrected, cbf */
>
> would not have been sufficient? What's the point of "wrapping"
> the numbers around the buffer, so to speak?

Because tail may be greater than end. In future, show complete
code, not snippets.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
cbfalconer at maineline dot net

--
Posted via a free Usenet account from http://www.teranews.com

wearyofallthiscrap@gmail.com
Guest
Posts: n/a

 06-27-2007
On Jun 26, 6:26 pm, CBFalconer <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
> > Calculating the size is being done with lines like this:

>
> > end = (head + (buffer_size - tail)) % buffer_size;
> > size = end;

>
> size = (tail - end) % buffer_size;

Um, no, the code I posted is copy and pasted from the source
file open in another window. It really does look exactly as I
posted. Yes, I know how it could be simplified. I left it
as it was coded because the names seemed meaningful.

> > Now, I understand (I think) why the math is ordered the way it is,
> > to avoid any potential integer overflow when "head + buffer_size"
> > would have been calculated. What I don't understand is why

>
> > size = tail - head; /* corrected, cbf */

No, unless you're reversing things midway, he original form was
in fact the question I wanted to ask. See Eric Sosman's reply
for what's going on -- and thank you, Eric, for the pointer! I

-Ti