Syscall 2: Firmware, home

DriverChapter 11: Capstones

D41OUT OF ORDER

The task

Deliver the numbered readings in number order, each as soon as it can go.

Readings reach the office over several relay paths, so they can arrive in any order. Each comes as two bytes: its number, then its value. The numbers start at 0 and have no gaps, and there are at most 30 of them.

Deliver the values to the host in number order. Deliver each one as soon as it and every reading numbered before it have arrived; while a number is still missing, hold the readings after it.

This card has 32 cells of RAM.

The board

The line card of OUT OF ORDERThe line card: registers A B C, 14 lines of ROM, 32 cells of RAM, a 16 byte receive buffer, a stack 8 deep. It talks to the line and to a host.LINETHE FAR ENDRXTXCARDREGISTERSA B CROM14 LINESRAM32 CELLSRX BUFFER16 BYTESSTACK8 DEEPUNITSNONEHOSTMESSAGES
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

RAM starts as zeros, so a cell that is still 0 is a reading that has not come yet.

Hints

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

Hint 1Show

Store each value in RAM at the cell its number names, and keep the number to deliver next in C.

Hint 2Show

A value can be 0, so mark the cells that hold a reading: OR A, $100 sets bit 8, and HOUT still delivers only the low byte.

Hint 3Show

IN B, IN A, OR A, $100, MOV [B], A. Then deliver cell C while it is not 0: MOV A, [C], JEQ A, 0, TOP, HOUT A, ADD C, 1, and loop.

Solution

Reveal the Full SolutionThe complete program for OUT OF ORDER. 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.

TOP:    IN B
        IN A
        OR A, $100
        MOV [B], A
EMIT:   MOV A, [C]
        JEQ A, 0, TOP
        HOUT A
        ADD C, 1
        JMP EMIT
TICKS
450
at par
LINES
9
at par