TAOCP 1.4.4 Exercise 3
Let two buffers for output be \texttt{OUTBUF1}, \quad \texttt{OUTBUF2}, each of length $100$ words.
Section 1.4.4: Input and Output
Exercise 3. [22] Write a buffer-swapping output subroutine analogous to (4). The subroutine, called WORDOUT, should store the word in rA as the next word of output, and if a buffer is full it should write 100 words onto tape unit V. Index register 5 should be used to refer to the current buffer position. Show the layout of buffer areas and explain what instructions (if any) are necessary at the beginning and end of the program to ensure that the first and last blocks are properly written. The final block should be filled out with zeros if necessary.
Verified: yes
Solve time: 50s
Solution
Let two buffers for output be
$$ \texttt{OUTBUF1}, \quad \texttt{OUTBUF2}, $$
each of length $100$ words. Let each buffer be used cyclically. Let a memory location $\texttt{CURBUF}$ contain the address of the buffer currently receiving output. The other buffer address is stored as the first word of each buffer, exactly as in (4), so that switching requires only a load from memory.
Index register $5$ holds the position within the current buffer. Its values range over $0,1,\dots,99$, and the $k$th stored word is placed at offset $k$ from $\texttt{CURBUF}$.
A buffer is full when index register $5$ reaches $100$ after an increment. At that moment, 100 words are written from the active buffer to tape unit $V$.
The layout is
$$ \begin{aligned} \texttt{OUTBUF1}:&\quad 100 \text{ data words} \ \texttt{OUTBUF2}:&\quad 100 \text{ data words} \end{aligned} $$
with $\texttt{OUTBUF1}$ containing the address of $\texttt{OUTBUF2}$ and $\texttt{OUTBUF2}$ containing the address of $\texttt{OUTBUF1}$ in their first word.
The subroutine $\texttt{WORDOUT}$ stores the word in $rA$ into the current buffer, advances the position, and triggers output when the buffer is full.
01 WORDOUT STA TEMP Save rA temporarily
02 INC5 1 Advance position in buffer
03 STA 0,5(CURBUF) Store word into current buffer
04 CMP5 =100= Test for full buffer
05 JNE DONE If not full, exit
06 OUT 0,5-100(V) Output 100-word block
07 JBUS *(V) Wait until output completes
08 LD5 =0= Reset position
09 LDA CURBUF Load current buffer address
10 LD6 1,0 Load address of other buffer
11 ST6 CURBUF Switch buffers
12 DONE LDA TEMP Restore rA
13 JMP * Return
The expression $\texttt{OUT 0,5-100(V)}$ denotes output of the block starting at the first word of the completed buffer; the subtraction of $100$ restores the base address since register $5$ equals $100$ at completion.
At program start, initialization must establish a valid buffer state before any call to $\texttt{WORDOUT}$. The required initial conditions are
$$ \texttt{CURBUF} \leftarrow \texttt{OUTBUF1}, \qquad r5 \leftarrow 0. $$
No output operation is initiated at this stage, since no buffer contains valid data.
At program termination, the final block may contain fewer than $100$ words. Let $k$ be the final value of register $5$ satisfying $0 \le k < 100$. The remaining positions $k+1,\dots,100$ are filled with zeros by repeated execution of
$$ \texttt{INC5 1; STA 0,5(CURBUF)} $$
with $rA \leftarrow 0$ until $r5 = 100$. After this padding, the same output sequence
$$ \texttt{OUT CURBUF(V); JBUS *(V)} $$
is executed once more to transmit the final block.
The subroutine maintains the invariant that exactly one buffer is active for accumulation and the other buffer is either idle or available for reuse. Each completed block is written exactly when its 100th word is stored, and no buffer is overwritten before its contents have been transmitted. This completes the proof. ∎