Circular Buffers

        Buffers are very commonly used devices in programing. They are areas of memory used to
hold data temporarily. A common use would be to read in a bunch of music data from a disk into a
buffer and then remove it byte by byte from the buffer as it is being played, because reading
from memory is faster than from disk.
        There are various types of buffers, and you would use a different one depending on the 
application. There are buffers from which all the information is put in and removed at once in 
one block and ones from which it is removed unit by unit, units being bytes, words, etc.
        The use of buffers from which the data is transfered in and out at once in one block is 
almost obvious. You simply allocate an area of memory, copy the data to it, then copy it out when 
you need it.
        However, most of the time, you must either put data in, take it out, or both, unit by 
unit. There are still several ways of doing this, and I will show you the circular buffer in a 
moment, but first, I will show the most basic, least thought-out way of doing this:

        ---------
   Out->|byte 0 |<-In
        |byte 1 |
        |...    |
        |...    |
        |byte 99|
        ---------

      The "Out" and "In" symbols represent the Out and In pointers, respectivly. The Out and In
pointers are variables which are not necessarily address pointers like the pointers in C or 
PASCAL, but are usually just integers which act as bookmarks to keep track of which spot in the 
buffer is to receive the next character and which is the one where the last character should be 
removed.
        Here is a pseudocode which shows how this buffer is operated:

variables
{
        Array of byte BUFFER with 100 elements;
        integer In,Out;
};

WriteToBuffer ( byte j )
{
        if In > 99 then Buffer Full
        else
        BUFFER[In] = j;
        In = In + 1;
};

byte ReadFromBuffer ( )
{
        if Out = In then Buffer Empty;Out = 0;In = 0;
        else
        Out = Out + 1;
        return ( BUFFER[Out - 1] );
};

        Note several things: 

        a) This buffer can hold a maximum of 100 items.

        b) This buffer requires that Out and In be reset to 0 when the are
           equal to allow you to hold the maximum number of items.

        c) In the function "ReadFromBuffer", the condition "Out = In" would
           be satisfied if:

           1) In and Out are at 0. (The Buffer is initialized)

           or

           2) In and Out are equal but not zero. (The Buffer is empty, but
              not initialized)

           or

           3) The buffer had been full and now Out has reached position 99
              also. (The buffer will is in a pre-overflow condition, i.e.
              it will not be able to receive any more bytes until it is
              initialized)

        d) In the function "WriteToBuffer", "Buffer Full" means that In has
           reached position 99 and no more can be written, it doesn't 
           necesarily mean that there are 100 bytes in the buffer.

        This buffer would work for quite a few applications, but many tasks require that the 
buffer be more efficient in its use of memory ( be able to take advantage of the memory freed 
when an item is removed, rather than have to wait until Out = In again) and be able to be run 
using smaller, faster code ( This code is small, but there is a better way to do it. )

        You have probably already figured out that all that needs to be done is for the In 
pointer to wrap around to position 0 again after reaching 99, providing that byte 0 has already 
been read out ( i.e., Out > 0 ).
This could be done with the addition of several "if" statements and would be a CIRCULAR BUFFER. 
Named so because it wraps around and never needs to be re-initialized after it is initialized in 
the beginning.
	Here is some pseudocode indicating how a circular buffer would work:        

variables
{
        Array of byte BUFFER with 100 elements;
        integer In,Out;
};

WriteToBuffer ( byte j )
{
        if Out = ( In + 1 ) MOD 100 then Buffer Full;
        else
        BUFFER[In] = j;
        In = In + 1;
        In = In MOD 100;
};

byte ReadFromBuffer ( )
{
        variable byte temp;
        if Out = In then Buffer Empty;
        else
        temp = BUFFER[Out];
        Out = Out + 1;
        Out = Out MOD 100;
        return ( temp );
};

        Note: MOD means Modulo Arithmetic. In the equation "C = A MOD B",
C = the remainder of A divided by B. The symbol for MOD in C is "%". In BASIC and PASCAL, the 
word "MOD" is used just as it has been used in the pseudocode. For the purposes of circular 
buffers, MOD can be implemented by just using an "if" statement or other conditional, like so:

byte MOD ( byte a , byte b)
{
	if a >= b then return (a-b)
	else return (a);
};
	This is not a truly mathematically correct modulo implementation, but it is faster than 
actually computing the remainder and it will return the right answer as long as a doesn't contain 
more than one multiple of b (i.e., if the quotient a/b is less than 2).

        I will list three statements about circular buffers which are important to know when  
using them:

        a) IF Out = ( In + 1 ) MOD BufferSize THEN Buffer is Full ( Currently 
        contains BufferSize number of entries )

        b) IF Out = In THEN Buffer is Empty ( Currently contains 0 entries )

        c) The formula for the number of entries currently in the Buffer
           is: ( ( BufferSize - Out ) + In ) MOD BufferSize

        Try these out by imagining a 10 byte buffer. You will remember
them very easily if you know how they work. Just remember that MOD allows you
to "wrap around" a variable when it reaches a certain value.