601.229 (F19): Homework 3: Machine-level Programming

Note: We will be posting solutions to this assignment on Tuesday, Oct 1st, so you may not use more than four late days on this assignment.

Update 9/26: clarified that the right_shift_n subroutine should shift in 0 bits (i.e., it is a logical shift)

Overview

In this assignment you will write machine-level programs for the SCRAM and 6502 and a disassembler for the SCRAM system.

There is also an interesting extra credit hardware design problem involving an implementation of SCRAM.

Expectation of original work

You might be able to find answers to all of these problems on the web. Please resist the temptation to do this, and understand that turning in work that is not your original work is a violation of academic integrity. All of these problems have straightforward solutions that you should be able to work out with a bit of thought and effort.

6502 and Logisim resources

See the Resources section of the Sec 02 CSF web page for some useful information about Logisim evolution and also the 6502 processor.

Problem 1: SCRAM programming (40%)

For this problem, your task is to write a SCRAM program that will multiply two 8 bit integers to produce an 8 bit product. Here are the requirements:

Once the program has completed the multiplication, it should execute a HLT (Halt) instruction, which has the instruction code 0. I.e., any instruction where the code bits (the 4 highest bits) are all zero will be treated as a HLT instruction.

You can test your program using a simple SCRAM simulator: scram.jar

To run the simulator, use the command

java -jar scram.jar "initial memory contents"

For initial memory contents, specify a sequence of byte values in hexadecimal to store in the SCRAM’s 16 memory locations.

As an example, here is the simulator running a program that adds the values 17 and 42, then stores the sum in memory location $F (15):

$ java -DmaxCycles=1000 -jar scram.jar "1D 5E 3F 00 00 00 00 00 00 00 00 00 00 11 2A 00"
Start: 1d 5e 3f 00 00 00 00 00 00 00 00 00 00 11 2a 00 A=00 PC=0
0000 : 1d 5e 3f 00 00 00 00 00 00 00 00 00 00 11 2a 00 A=11 PC=1
0001 : 1d 5e 3f 00 00 00 00 00 00 00 00 00 00 11 2a 00 A=3b PC=2
0002 : 1d 5e 3f 00 00 00 00 00 00 00 00 00 00 11 2a 3b A=3b PC=3
0003 : 1d 5e 3f 00 00 00 00 00 00 00 00 00 00 11 2a 3b A=3b PC=4
Halted after 4 cycles

The simulator shows the initial machine state (labeled Start:), and then shows the machine state after each time step of the simulation. The machine state consists of the values of the 16 memory locations and the value of the accumulator (A) and program counter (PC). All values are displayed in hexadecimal. Note that when the simulation terminates (due to the execution of the HLT instruction at address $3), the sum $3b (decimal 59) is stored at address $F.

You can use the -DmaxCycles= option to specify an upper limit on the number of program instructions to be executed. This is useful in case your code has a runaway loop.

The first component of your submission for this problem should be a plain text file called Problem1MachineCode.txt containing a sequence of hexadecimal bytes (i.e., the initial memory contents.) For example, if you were submitting a program to add the numbers 17 and 42 and store the sum at address $F (which you’re obviously not, this is just an example of the expected format!), the contents of your Problem1MachineCode.txt might be:

1D 5E 3F 00 00 00 00 00 00 00 00 00 00 11 2A 00

Extremely important: Problem1MachineCode.txt should contain only memory content bytes. Do not put your name and email address in this file!

Note that you can specify whatever data values you want for the operands at addresses $D and $E. However, you should assume that we will test your program with a variety of data values, by changing the values stored at these locations.

You should also submit a plain text file called Problem1AssemblyCode.txt that contains an assembly language version of your program. For example, the assembly language for the 17+42 program might look like this:

J. Student
jstuden1@jhu.edu

                     ; Awesome SCRAM program to compute 17+42

0: 1D        LDA D   ; load first operand to accumulator
1: 5E        ADD E   ; add second operand to accumulator
2: 3F        STA F   ; store sum at $F
3: 00        HLT     ; end of program
4: 00                ; unused
5: 00                ; unused
6: 00                ; unused
7: 00                ; unused
8: 00                ; unused
9: 00                ; unused
A: 00                ; unused
B: 00                ; unused
C: 00                ; unused
D: 11                ; data operand 1 (17)
E: 2A                ; data operand 2 (42)
F: 00                ; storage for sum

The exact format of your assembly code listing isn’t critical, but it should indicate the encoding of each code and data byte, and show the assembly code for bytes containing program instructions.

Problem 2: SCRAM disassembler (15%)

Your task for Problem 2 is to write a disassembler program for the SCRAM. Your program must be a C program in a source file called Problem2.c.

The program should read up to 16 binary data bytes from standard input and print one line of output for each input byte. Each output byte should be the disassembly of the input byte as a SCRAM instruction.

Here are the SCRAM instruction codes, which you will find in the highest four bits of each byte:

Code Name
0 HLT
1 LDA
2 LDI
3 STA
4 STI
5 ADD
6 SUB
7 JMP
8 JMZ

The exact format of a dissassembly line is as follows:

X: III D

X is a hexadecimal digit indicating the address of the instruction. Use a–f for values 10–15.

III is the instruction name. Use all upper case letters for the names of the valid instruction codes, 0–8. Instruction codes 9–15 are not valid instructions, and should be printed as ???.

D is the data value in bits 0–3 of the instruction. It should be printed as a single hexadecimal digit (again, use a–f for values 10–15.)

Your program should print an error message and exit with a non-zero exit code if there are more than 16 bytes of input. Note that less that 16 bytes of input is fine (see example input 2.)

Example input 1

The file sum_17_plus_42.bin contains the exact binary data for the example program from Problem 1. To run your program on this input (assuming the executable is called Problem2), run the command

./Problem2 < sum_17_plus_42.bin

The output of this command should be

0: LDA d
1: ADD e
2: STA f
3: HLT 0
4: HLT 0
5: HLT 0
6: HLT 0
7: HLT 0
8: HLT 0
9: HLT 0
a: HLT 0
b: HLT 0
c: HLT 0
d: LDA 1
e: LDI a
f: HLT 0

Note that your disassembler will not know which bytes are actual instructions and which just contain data: it assumes that every byte is an instruction.

Example input 2

The file funky_input.bin contains some data bytes that aren’t valid instructions, and also contains only 7 bytes of data. The command

./Problem2 < funky_input.bin

should produce the output

0: HLT 6
1: ??? 4
2: ADD e
3: ??? 2
4: ??? 0
5: LDI f
6: ??? 4

Problem 3: 6502 programming (45%)

In this problem you will write two 6502 assembly language subroutines.

Each assembly language program should be in a text file called Problem3X.asm, where X is the subproblem (a or b.)

All of your assembly subroutines must assemble and run correctly in Easy 6502.

When testing each routine, you will find it useful to add test setup code. For example, lets say you’re writing a subroutine called addfortytwo whose purpose is to add 42 to the parameter X and return the sum in the accumulator. Your test code and function might look like this:

entry:
    LDA #$11      ; test data value
    TAX           ; put test data value in X
    JSR addfortytwo
    BRK

; Return the value of X plus 42 in the accumulator.
addfortytwo:
    TXA            ; put arg in accumulator
    CLC            ; clear carry flag
    ADC #$2A       ; add 42 to accumulator
    RTS

If you paste this code into Easy 6502, the click Assemble followed by Run, you will see this:

Easy 6502 screenshot

Note how the value of the A (accumulator) register is $3b (decimal 59), and is the correct sum of the test data value $11 (decimal 17) and 42.

(a) Write a subroutine called popcount. It should return (in the accumulator) the total number of bits in the X register that are set to 1.

For example:

LDA #$5C
TAX
JSR popcount
; at this point, A will contain the value 4

(b) Write a subroutine called right_shift_n. It should shift the bits in the accumulator right by the number of bits specified by the value in the X register.

For example:

LDA #$02    ; shift right by 2 bits
TAX         ; put the shift amount in the X register
LDA #$5C    ; put the data value $5C in the accumulator
JSR right_shift_n
; at this point, A will contain the value $17

Note that the bits shifted into the accumulator (as the new high bits) should all be zero. This implies that if the value passed in the X register is 8 or greater, then A will be 0 when the subroutine returns.

Problem 4: SCRAM hardware (5% extra credit!)

This is an extra credit problem! Make sure you complete the other problems before attempting this problem.

The Logisim evolution file demoSCRAM2.circ contains a partial implementation of the SCRAM machine, in the circuit called “SCRAM7”.

Complete the implementation of this machine by adding support for the SUB, JMP, and JMZ instructions, as described in the SCRAM handout.

Notes and hints:

Submit your work for this problem in a file called Problem4.circ, which is your Logisim file containing the completed design.

Submitting

Prepare a zipfile with your files and upload it to Gradescope as HW3. Make sure your files are in the top level of the zipfile, i.e., they should not be in a subdirectory.

If you did not do Problem 4 (the extra credit problem), then you should use the command

zip hw3.zip Problem1MachineCode.txt Problem1AssemblyCode.txt Problem2.c Problem3a.asm Problem3b.asm

and then upload hw3.zip.

If you did do Problem 4, then you should use the command

zip hw3.zip Problem1MachineCode.txt Problem1AssemblyCode.txt Problem2.c Problem3a.asm Problem3b.asm Problem4.circ

and then upload hw3.zip.

Don’t forget to put your name and JHU email address in each file if appropriate, but do not put them in Problem1MachineCode.txt.

Grading

For reference, here is a short explanation of the grading criteria; some of the criteria don’t apply to all problems, and not all of the criteria are used on all assignments.

Packaging refers to the proper organization of the stuff you hand in, following both the guidelines for Deliverables above as well as the general submission instructions for assignments on Piazza.

Style refers to C and assembler programming style, including things like consistent indentation, appropriate identifier names, useful comments, suitable documentation, etc. Simple, clean, readable code is what you should be aiming for. Please see the Coding style guidelines.

Design refers to proper modularization (functions, modules, etc.) and an appropriate choice of algorithms and data structures.

Performance refers to how fast/with how little memory your programs can produce the required results compared to other submissions.

Functionality refers to your programs being able to do what they should according to the specification given above; if the specification is ambiguous, ask for clarification! (It also refers to you simply doing the required work, which may not be programming alone.)

If your programs cannot be built you will get no points whatsoever. If your programs cannot be built without warnings using the required compiler options given on Piazza we will take off 10% (except if you document a very good reason). If your programs cannot be built using make we will take off 10%. If valgrind detects memory errors in your programs, we will take off 10%. If your programs fail miserably even once, i.e. terminate with an exception of any kind or dump core, we will take off 10% (for each such case).