TAOCP 1.4.4 Exercise 7
Let each buffer contain exactly $100$ consecutive words.
Section 1.4.4: Input and Output
Exercise 7. [22] Write a subroutine called WORDIN that is essentially like (4) except that it does not make use of a sentinel.
Verified: yes
Solve time: 50s
Solution
Let each buffer contain exactly $100$ consecutive words. Let $\beta_1$ denote the base address of INBUF1 and $\beta_2$ the base address of INBUF2. Let the word in each buffer that formerly contained SENTINEL be replaced by a constant equal to the first location after the usable portion of that buffer; thus define
$$ L_1 = \beta_1 + 100, \qquad L_2 = \beta_2 + 100. $$
Each buffer also contains, as in (4), the address of the other buffer.
The goal is to remove the sentinel test and instead detect exhaustion of the buffer by comparing the current index against the fixed upper bound of the block.
Index register $6$ is again used as the pointer to the current input word. After each call to WORDIN, register $6$ is incremented once. The buffer is exhausted exactly when the incremented value equals the limit $L_i$ of the active buffer.
The modified subroutine replaces the equality test against SENTINEL by an equality test against the buffer limit.
01 WORDIN STJ 1F Store the exit location.
02 INC6 1 Advance to the next word.
03 2H LDA 0,6 Load current word.
04 CMPA =LIMIT= Is end of buffer reached?
05 1H JNE * If not, exit.
06 IN -100,6(U) Refill this buffer.
07 LD6 1,6 Switch to the other buffer.
08 JMP 2B Return.
09 INBUF1 ORIG *+100 First buffer
10 CON L1 End-of-buffer address
11 CON *+1 Address of other buffer
12 INBUF2 ORIG *+100 Second buffer
13 CON L2 End-of-buffer address
14 CON INBUF1 Address of other buffer
The constant LIMIT used in line 04 is interpreted as the value stored in location 10 for INBUF1 or location 13 for INBUF2, depending on which buffer is active. The instruction LD6 1,6 switches the index register to the other buffer, so the correct limit is then used on the next invocation.
Correctness follows from the fact that the buffer is traversed sequentially via INC6, so the register $6$ takes exactly the sequence of addresses of the active buffer. The comparison in line 04 detects exhaustion exactly when $6 = L_i$, which occurs after the last valid word has been consumed. At that point, the IN instruction refills the same buffer area, and control is transferred to the alternate buffer whose base and limit are stored in its first two words. This restores the invariant that index register $6$ always points within the active buffer after refill.
This completes the proof. ∎