Array index subtraction and wrapping

Discussion in 'C Programming' started by wearyofallthiscrap@gmail.com, Jun 26, 2007.

  1. Guest

    (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.

    The buffer uses head (writing) and tail (reading) offsets.
    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?
     
    , Jun 26, 2007
    #1
    1. Advertising

  2. Eric Sosman Guest

    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.
    >
    > The buffer uses head (writing) and tail (reading) offsets.
    > 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
    have been read, so tail = 50. (I'm assuming that head
    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
    often there are two "active" positions -- like your head
    and tail -- but sometimes there may be three or more.
    (I've never seen more than four used, but I bet someone
    has.)

    --
     
    Eric Sosman, Jun 26, 2007
    #2
    1. Advertising

  3. CBFalconer Guest

    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.
    >
    > The buffer uses head (writing) and tail (reading) offsets.
    > 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
     
    CBFalconer, Jun 26, 2007
    #3
  4. Guest

    On Jun 26, 6:26 pm, CBFalconer <> wrote:
    > wrote:
    > > The buffer uses head (writing) and tail (reading) offsets.
    > > 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
    now know more about circular buffers than I had ever thought. :)


    -Ti
     
    , Jun 27, 2007
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    7
    Views:
    586
    Neredbojias
    Mar 31, 2007
  2. Replies:
    9
    Views:
    716
    Christopher Bazley
    Jan 30, 2010
  3. Nicko
    Replies:
    10
    Views:
    209
    Robert Klemme
    Jun 11, 2007
  4. Shawn W_
    Replies:
    5
    Views:
    320
    Aldric Giacomoni
    Sep 16, 2009
  5. Tomasz Chmielewski

    sorting index-15, index-9, index-110 "the human way"?

    Tomasz Chmielewski, Mar 4, 2008, in forum: Perl Misc
    Replies:
    4
    Views:
    356
    Tomasz Chmielewski
    Mar 4, 2008
Loading...

Share This Page