Ring Buffer

A ring buffer is a fixed block of memory used as a queue: a write index and a read index each advance through it and wrap to the start when they reach the end, so the block never has to grow or move. It is old computer-science vocabulary — BYTE was explaining it to hobbyists in 1977 — and it turns up in period game code wherever something has to be remembered for a fixed number of frames and then forgotten. The example held here is an echo effect in one of Tim Follin’s Spectrum beeper engines.

Fast facts

• Definition (BYTE, 1977): “conceptually a ring although in memory it is actually a region from HEAD to TAIL”, with an IN pointer for the next free slot and an OUT pointer for the next slot to process.
• Hardware equivalent: the FIFO memory chip, per the same article.
• In a game: the 16-entry delay line (ECTA) in the Agent X II music engine, wrapped with AND 15.
• In a system: Amiga Exec’s device interrupts “deposit raw data into bounded or circular buffers”, which “overflow or wrap around” if nobody drains them.

The idea, as BYTE explained it

G H Gable’s January 1977 article on adding interrupt-driven terminal I/O to his monitor program set out the two shapes a buffer can take. A linear buffer is a region from HEAD to TAIL walked once by a single pointer. A circular buffer keeps two pointers: “The IN pointer gives the next available location, and the OUT pointer gives the next location to be used by a processing program.” Interrupt handlers write at IN; the program reads at OUT; both wrap. Gable added that “in hardware, a circular buffer corresponds roughly to an integrated circuit called the first in first out memory, sometimes abbreviated FIFO.”

The structure is a good fit for anything produced and consumed at different rates — characters arriving from a keyboard or serial port, samples for an audio device — because the producer never waits for the consumer and the memory cost is fixed in advance. The price is that a full buffer must either refuse new data or overwrite the oldest.

A ring buffer in a Spectrum music engine

Tim Follin’s engine for Agent X II (Mastertronic, £1.99; reviewed in Crash’s Christmas 1987 special, which called the first-level tune “superb”) produces an echo by remembering what each note was a fixed number of frames ago. The source, recovered from Follin’s Tatung Einstein development disks, declares a 49-byte table ECTA and fills it as sixteen three-byte entries. Every frame the write index is advanced and masked:

POINT:LD A,000
      INC A
      AND 15
      LD (POINT+1),A

The current note’s state — three bytes taken from the operands of other instructions in the engine — is copied into the slot at that index. The read-back position is the write index minus a delay, masked the same way:

      LD A,(POINT+1)
DELAY:SUB 015
      AND 15
      LD HL,ECTA

What comes back is the note as it was fifteen frames earlier, which the engine re-injects at reduced volume behind the live voice. Two details are characteristic of the period. The index is stored in the operand byte of the LD A,000 instruction and rewritten in place — self-modifying code standing in for a variable — and the AND 15 mask does the wrapping, which only works because the entry count is a power of two.

Where a system kept them

The Amiga’s Exec kernel used the same structure between interrupt handlers and the device tasks that served them. The ROM Kernel Reference Manual warns programmers calling the Wack debugger — which stops multitasking but leaves interrupts running — that “many interrupts deposit raw data into bounded or circular buffers”, that device tasks normally drain them, and that with those tasks halted the buffers “may begin to overflow or wrap around” if the user keeps typing. The keyboard buffer being described is Gable’s diagram twenty years on, with the processing program suspended.

See also

• Beeper music
• Audio programming
• Self-modifying code
• Object pooling
• Tim Follin
• ZX Spectrum