Syscall 2: Firmware, home

DriverChapter 12: Shared buses

D50ELASTIC BUFFER

The task

Transmit every received byte on a slower line, in order, without losing any.

Bursts from the depot's fast line arrive at one byte every 10 ticks, but the old line out to the yard takes 20 ticks for each byte. Between bursts there is time to catch up, but the receive buffer holds only 4 bytes.

Transmit every received byte, in order. OUT waits for the line to be free and the card can do nothing else meanwhile, so keep a queue of your own in RAM and transmit only when 20 ticks have passed since the last OUT.

A burst is at most 24 bytes. This card has 32 cells of RAM, RXN reads how many received bytes are waiting, and CLK reads the tick counter.

The board

The line card of ELASTIC BUFFERThe line card: registers A B C D, 20 lines of ROM, 32 cells of RAM, a 4 byte receive buffer, a stack 8 deep, and CLOCK. It talks to the line.LINETHE FAR ENDRXTXCARDREGISTERSA B C DROM20 LINESRAM32 CELLSRX BUFFER4 BYTESSTACK8 DEEPUNITSCLOCK
The line card this ticket gives you, with its registers, memory, buffers, and units. On a narrow screen, scroll the board sideways to see all of it.

Key idea

The queue is elastic: it stretches during a burst and shrinks while the line is quiet. Only its size limits how long a burst may be.

Hints

Each hint goes a step further than the one before. Open them one at a time.

Hint 1Show

Keep a ring in RAM: write at B, read at C, and after each step AND the index with 31 so it wraps from 31 back to 0. The queue is empty when B equals C.

Hint 2Show

Keep in D the tick when the line will be free. After OUT, MOV D, CLK, then ADD D, 20. Before OUT, compare CLK with D; JLT is safe since the clock stays far below 32768.

Hint 3Show

LOOP: if RXN is not 0, IN A, store it at [B], and step B. Then if B is not C and CLK is not below D, MOV A, [C], OUT A, step C, and set D. Back to LOOP either way.

Solution

Reveal the Full SolutionThe complete program for ELASTIC BUFFER. Open it only when you want the answer.

The reference program

The game's own solution to this ticket. It passes every test and scores exactly par on every benchmark.

LOOP:   JEQ RXN, 0, SEND
        IN A
        MOV [B], A
        ADD B, 1
        AND B, 31
SEND:   JEQ B, C, LOOP
        MOV A, CLK
        JLT A, D, LOOP
        MOV A, [C]
        OUT A
        ADD C, 1
        AND C, 31
        MOV D, CLK
        ADD D, 20
        JMP LOOP
TICKS
1894
at par
LINES
15
at par