Ring Buffer Routines




This  package  consists  of  a  set  of  fairly  fast assembly-language
procedures  for  buffering  data by  means  of  circular  buffers.  The
package comes  in two  versions: a  "byte" version  (RingBytes.br) that
deals with  bytes and  packs them two  per word,  and a  "word" version
(RingWords.br) that deals with  full words.  The procedures in  the two
packages  are  called identically,  so  one may  substitute  the "word"
version for the "byte" version to  gain about a factor of two  in speed
at the cost of using buffer space only half as efficiently.  The binary
files  mentioned above  are contained  in <Alto>RingBuffer.dm,  and the
source files are in <AltoSource>RingBuffer.dm.  A Nova version  of this
package is available.

A ring buffer is described by a Ring Buffer Descriptor (RBD),  which is
the  address  of  a  4-word  patch  of  memory  provided  by  the user,
initialized through a call to InitRingBuffer, and thereafter maintained
by the routines in the package.  The "byte" and "word" versions  of the
routines make different uses of the RBD, but this is of no  interest to
callers.

InitRingBuffer(RBD,Buffer,Length)
    Initializes  the RBD  to describe  a block  of storage  starting at
    "Buffer" and of length "Length" (in words).

ResetRingBuffer(RBD)
    Renders the ring buffer described by RBD empty.

RingBufferEmpty(RBD) = true or false
    Returns true if the buffer is empty.

RingBufferFull(RBD) = true or false
    Returns true if the buffer is full.

ReadRingBuffer(RBD) = Item (byte or word)
    Returns the next Item in the ring buffer if there is one, or  -1 if
    there isn't.  Obviously,  if the "word"  version of the  package is
    being used and -1 is a possible Item, then the caller  should check
    with RingBufferEmpty before calling ReadRingBuffer.

WriteRingBuffer(RBD,Item) = true or false
    Attempts  to put  Item into  the ring  buffer and  returns  true if
    successful.  The  "byte" version of  this procedure depends  on the
    left half of Item being zero.

When these routines are used to pass streams of data between interrupt-
level and non-interrupt-level code, the following precautions should be
observed to avoid races:

1.  For a given RBD, neither ReadRingBuffer nor  WriteRingBuffer should
be  called  both from  interrupt  level and  from  non-interrupt level.
However,  ReadRingBuffer  may  be  called  from  interrupt   level  and
WriteRingBuffer from non-interrupt level or vice versa.


                             ------------
                   Copyright Xerox Corporation 1979


Ring Buffer Routines       February 20, 1976                          2




2.   InitRingBuffer  and  ResetRingBuffer  should  not  be  called from
interrupt level.

3.  Calls to all routines should be made with interrupts on, since some
of them execute "dir" and "eir" internally.  (This is not a  problem if
the BCPL Interrupt Package is being used.)

The following information is provided for debugging purposes  only, and
one should not write code that depends on it.

The "byte"  version of the  package lays out  the RBD in  the following
way:

    structure RBD: [
        Begin word      // Pointer to start of buffer
        Length word     // Buffer size in bytes
        Read word       // Current read index
        Write word      // Current write index
        ]

The buffer is treated  as an array of  bytes, packed left to  right and
indexed starting at zero.  The Read and Write indices refer to the last
byte read or written.

The "word" version of the package uses the RBD in this way:

    structure RBD: [
        Begin word      // Pointer to start of buffer
        End word        // Pointer past end of buffer
        Read word       // Current read pointer
        Write word      // Current write pointer
        ]

The End word  points to the  first word beyond  the end of  the buffer;
i.e. its value is  Begin plus the length  of the buffer.  The  Read and
Write pointers point to the next word to be read or written.

Rough timings for the  important procedures are now given.   The counts
are  simply  number   of  instructions  executed,  not   including  the
instruction that called the procedure.

                             "byte"              "word"
    RingBufferEmpty          9                   9
    RingBufferFull           10                  11
    ReadRingBuffer           20.5 normally       12 normally
                             9 if empty          9 if empty
    WriteRingBuffer          25 normally         13 normally
                             13 if full          13 if full