K. Punchcard (2800 points)

Some people strongly believe that the only durable data storage is paper. A popular way to store data on paper is using punch cards or punch tapes. If we already have a processor controlled device that can read/write the cards, we can use spare resources to implement stand-alone applications. To demonstrate the idea, a minimalistic implementation is provided for testing during the 24 hours of the contest.

The firmware provides access to a custom 4-bit processor and is programmed to read programs from punch cards then process data cards running the program. Teams shall submit programs on paper. To avoid producing excess amount of little paper cutouts, we use pens to mark holes on the paper: a black solid mark means 1, no mark means 0. Marks should be at least 4 mm in diameter.

4-bit CPU specification

This is a 4-bit computer, handling nibbles. Whenever multiple nibbles are stored and handled as a single number, the first nibble contains the least significant bits; bits from left to right in a nibble is MSB -> LSB. Example: "0001 1010" as a 8 bit unsigned value is 161 in decimal. The only exception is when explicitly specified otherwise.

4-bit Registers

code name description
0 A acc
1 STATUS status SDZC: SI page, DI page, zero, carry
2 SI source index
3 DI destination index

Instruction set summary

0000 LDAS move [SI] to A
0001 STAD move A to [DI]
0010 ADDAD add A to [DI], store result in [DI]; updates C and Z
0011 ADDAA add A to [DI], store result in A; updates C and Z
0100 ADDADC add A to [DI] and C, store result in [DI]; updates C and Z
0101 ADDDAC add A to [DI] and C, store result in A; updates C and Z
0110 ADDSDC add [SI] and [DI] and C, store result in [DI]; updates C and Z
0111 NOP no operation
1000 iiii LDA i load A with immed
1001 iiiiiiii JMP i jump to address i
1010 INVALID (invalid instruction)
1011 iiiiiiii CALL i absolute call to address i
1100 rrbb BTC r,b set bit b in register r to 0
1101 rrbb BTS r,b set bit b in register r to 1
1110 ddss MOVE d,s move value from register s to register d
1111 0000 LDAD move [DI] to A
1111 0001 STAS move A to [SI]
1111 0010 RET return from call
1111 0011 NAND nand A to [SI], store result in A
1111 0100 SKZ skip next instruction if Z
1111 0101 SKC skip next instruction if C
1111 0110 LOOPI decrement CNTR, increment SI, increment DI; skip next instruction if CNTR is zero;
1111 0111 LOOP decrement CNTR, skip next instruction if zero
1111 1011 SBAD sub A from [DI], store result in [DI]; updates C and Z
1111 1100 SBDA sub A from [DI], store result in A; updates C and Z
1111 1101 DECA decrement A
1111 1110 INCA increment A
1111 1111 FIN task finished
Syntax used in the table: [SI] or [DI] means internal random access memory (RAM) or one-time-programmable memory (OTP, paper) indexed by SI or indexed by DI (indirect memory access). Whether RAM or OTP is used depends on S and D bits of the STATUS register (see below).

Data memory

RAM map (page 0):
0 RAM0: ram
1 RAM1: ram
2 RAM2: ram
3 RAM3: ram
4 RAM4: ram
5 RAM5: ram
6 CNTR: counter
7 IPHI: instruction pointer high
8 IPLO: instruction pointer low
9 IPHD: in: phototransistors (data)
10 IBIN: in: bin (3210; 0: index; 1: paper end A; 2: paper end B; 3: )
11 OVOL: out: SPK volume
12 OFRQ: out: SPK freq
13 ODIR: out: in linear mode motor directions (3210; 0:- 1=paper_seek 1: pen 0=up 1=down; 2: 0=pen left 1=pen right 3: 0=paper+ 1=paper-); in seek mode target row
14 OMOV: out: motor enable (3210; 0: mode 0=linear move 1: allow pen; 2: allow left/right; 3: allow paper)
15 DLY: if >0, delay DLY cycles and set DLY to 0
Any non-ram is device mapped in. in devices should not be written. See how to handle IPHI and IPLO writes below.

memory map (page 1): 0..15: OTP slots on paper

Code memory size: at most 100 nibbles

code memory: 128 nibbles

Reset condition: IP (among with IPLO, IPHI), A, STATUS, SI and DI are all reset to 0. Content of other registers in the internal ram is unspecified. Content of the OTP depends on the input. Code memory beyond the submission length is filled with invalid instructions (to avoid leakage of other team's code).

IPHI and IPLO

IP is updated after the current instruction is already fetched from the code memory. The current instruction thus can access the address of the next instruction in IPHI and IPLO. In case the instruction modifies IPHI or IPLO the very next instruction will be fetched from the new address.

Submission

cards

Cards are preprinted forms on 297*63 mm stripes of paper. There are two type of cards: code and data. Bits on the code cards need to be filled in by the teams using the provided thick tip black pens. Teams may request code cards any time during the contest. Header fields of the code card needs to be filled in using a thin tip pen:

The leftmost column of preprinted black circles is the index column. Four bits of data is stored in each horizontal row that lines up with such an index dot. Data bits are either left white (for value 0) or marked (for value 1). A marking should be a solid black circle of 4..5 mm in diameter.

The first two rows of the first page (row 0 and 1) of the submission encodes the size of the submission (first row is the least significant nibble; leftmost bit in a row is the most significant bit of the nibble; the size and CRC nibbles are not added to this size). Row 2 contains a CRC calculated for the rest of the lines up to size. Because of the limit on code size, a submission is never longer than 5 pages.

Data cards look exactly like code cards but are marked as data and will be fed in the device after all code cards for a given program. A program consists any amount of code cards between 1 and 5 (inclusive) and a single data card.

CRC

The pseudo-code of the 4 bit CRC algorithm is

function crc4(nibbles[], len)
	crcpoly := 0x3
	crc := 0

	for i := 0 to len - 1 do
		crc := crc xor nibbles[i]
		for j := 0 to 3 do
			crc := crc * 2
			if (crc and 0x10) != 0 then
				crc := crc xor crcpoly
			end
		end
	end
	crc := crc and 0xf
	return crc
end

submission procedure

Teams submit their solution by handing over a full set of code cards to the operator who places the set in the input queue and enters team/cookie/taskid information into the database where the submission is marked as pending. Eventually the submission will get feeded in the device by the operator when the device becomes available. After all code cards for a submission are read by the device, it will calculate the CRC and stops with error if it does not match the CRC on row 2 on the first page. When CRC matches, the operator takes a data card with preprinted input data, fills in the header with team name and submisson cookie and feeds it in the device. The device will then start executing the code, reading and writing the data card in random access mode. When a FIN instruction is executed, the device stops and beeps and the operator removes the data card. After evaluation, the operator enters the result of the submission (score) into the database, where the team/cookie/taskid state will be changed from pending to evaluated. Data cards for test-run submissions are collected by the operator in an unlimited result queue and teams may pick up their data cards (among with their old code cards) any time during the contest. Data cards of for-score submissions are discarded.

Since the capacity of the hardware is limited, submissions are accepted only in the first 23 hours of the contest. There is an input queue for the hardware; each team may have a single submission in the queue. A team may cancel its last submission and add a new one, but that will be added at the end of the queue. When the device becomes available, the operator will always take the first submission in the queue. Runtime is accounted from the time the data card was succesfully inserted. If a program does not finish within a predefined timeout, evaluation of the submission is interrupted and the result is "failure due timeout".

Furthermore, for-score submissions always have priority over test-run submissions. In emergency cases (queue grows too long near the end of the contest or hardware failure), organizers may decide to evaluate submissions on a simulated device.

test-run submission

In test-run submissions teams submit both code cards and data card. After the evaluation the team gets back all cards. The team does not get any score by this method. This method is provided for allowing teams to debug their code on the real device in an off-line manner.

for-score submission

When a team is ready with a task, a for-score submission should be entered in the queue. In this case the team submits all code cards for the task and organizers provide a data card. At the end of the evaluation, the team will learn how the code finished (i.e. by running the FIN instruction, timeout, or other error). In case of a succesful execution (program ends with FIN within time), the organizers evaluate the output on the data card and also report whether the result is correct or not, and in case of a correct result, the team gets scores for the input (and no more submission is accepted for the same input). Teams can not read the data cards of for-score submissions.

trace submission

A simple web interface is provided for submitting cards containing at most 10 nibbles. In return the server dumps a trace. This service should be used to find out how the CPU works. The specification is as complete as it can be at this point, any question about how the CPU handles a specific instruction shall be checked on the trace submission server.

Tasks

Each task is worth 400 points.
# task, input, output
1 add two 16 bit numbers

input on paper:
4..7: op1 (MSB first)
8..11: op2 (MSB first)

output on paper:
0..3: sum (MSB first)

2 sum N 4 bit numbers in a 8 bit accumulator with overflow detection

input on paper:
3: number of operands (N)
4..N+4: operands

output on paper:
0: sum, least significant nibble
1: sum, most significant nibble
2: non-zero on overflow

3 find largest 4 bit number in input

input on paper:
1: number of operands (N)
2..N+2: operands

output on paper:
0: largest number

4 count zero bits in a nibble

input on paper:
0: input nibble

output on paper:
1: number of zeros in input

5 logical operation: rotate right (4-bit). Shift bits one position to the right; LSB falling out on the right should come back in from the left (MSB).

input on paper:
0: input nibble

output on paper:
1: rotated nibble

6 logical operations: shift right (4-bit). Shift bits one position to the right, discarding excess LSB bit. MSB filler bit is 0.

input on paper:
0: input nibble

output on paper:
1: shifted nibble

7 Print human-readable roman numbers, readable when card is rotated 90 degrees CW or CCW. For 0 use normal arabic 0.

input on paper:
0: input number between 0 and 3 (inclusive)

output on paper:
from 1: roman digits
There shall be one empty line between each roman digit. 0 is 'f9f', I is 'f'.