Machine Language

The Elements of Computing Systems

Tue 7th January 2020

Table of Contents

  1. Machines
  2. Commands
    1. Memory Access
  3. Hack
    1. Memory
    2. Registers
    3. Example code
    4. The A-Instruction
    5. The C-Instruction
      1. Comp
      2. Dest
      3. Jump
    6. Symbols
    7. Input/Output Handling
  4. Exercises
    1. Multiply
    2. Fill

Machines

A machine language manipulates memory using a processor and some registers. Memory is a continuous array of cells (or words) that each have a unique address. Registers are high-speed memory close to the processor. A Processor performs operations on the memory and registers.

Commands

The available commands fall into a few categories.

Memory Access

Memory access comes in a few addressing modes.

Immediate addressing is used to load constants:

LOADI R1, 67

This loads the value 67 into register `.

Direct addressing is used to load the data at the given address:

LOAD R1, 67

This loads into register 1 the value in memory at address 67.

Indirect addressing is used to load the data pointed to by the memory location:

LOAD* R1, R2

This loads whatever was pointed to by register 2 into register 1.

Hack

Hack is the computer we’ll be creating. Hack is a 16-bit machine with separate instruction and data memory.

Memory

Each address space (instruction and data) can hold 32K words. This means that addresses are 15 bits long ($2^{15}=32,768$). Instruction memory is read only.

Registers

There are two registers, A and D. A can store data or addresses, D can only store data.

Since Hack addresses are 15-bits and Hack instructions are 16-bits, we can’t fit an opcode and an address in the same instruction. Therefore, for any instruction that operates on memory, we will first store the address in A, and then operate on the memory stored there.

Similarly, direct jump instructions won’t contain their target, but will instead jump to the address stored in A.

Example code

// Adds 1+...+100.
    @i // i refers to some mem. location.
    M=1 // i=1
    @sum // sum refers to some mem. location.
    M=0 // sum=0
(LOOP)
    @i
    D=M // D=i
    @100
    D=D-A // D=i-100
    @END
    D;JGT // If (i-100)>0 goto END
    @i
    D=M // D=i
    @sum
    M=D+M // sum=sum+i
    @i
    M=M+1 // i=i+1
    @LOOP
    0;JMP // Goto LOOP
(END)
    @END
    0;JMP // Infinite loop

The A-Instruction

The A-Instruction (written @value), stores a 15-bit value in the A register. The first bit is zero, the rest are the values.

0000000000000101
|^^^^^^^^^^^^^^^- binary for 5
^- 0 signifying A-instruction

The above instruction would store 5 in the A register.

The C-Instruction

The C-Instruction (written without an @) has the form dest=comp;jump, where various bits may be missing. The first bit is one, and the next two bits are unused.

1xxaccccccdddjjj
|||||||||||||^^^- jump (3)
||||||||||^^^- dest (3)
|||^^^^^^^- comp (7)
|^^- unused (2)
^- 1 signifying A-instruction

Comp

The a and 6 c bits mean we could have $2^7=128$ different instructions, but we’re only going to use 28 of them. The a bit determines (for applicable instructions) whether the other operand (other than D) is A or Memory[A]. When a is 0, the other operand is A, when a is 1, the other operand is Memory[A].

a=0  c1 c2 c3 c4 c5 c6  a=1
0     1  0  1  0  1  0
1     1  1  1  1  1  1
-1    1  1  1  0  1  0
D     0  0  1  1  0  0
A     1  1  0  0  0  0  M
!D    0  0  1  1  0  1
!A    1  1  0  0  0  1  !M
-D    0  0  1  1  1  1
-A    1  1  0  0  1  1  -M
D+1   0  1  1  1  1  1
A+1   1  1  0  1  1  1  M+1
D-1   0  0  1  1  1  0
A-1   1  1  0  0  1  0  M-1
D+A   0  0  0  0  1  0  D+M
D-A   0  1  0  0  1  1  D-M
A-D   0  0  0  1  1  1  M-D
D&A   0  0  0  0  0  0  D&M
D|A   0  1  0  1  0  1  D|M

The left and rightmost columns display give the instructions when a=0 and a=1 respectively. The middle columns give the bit values for those instructions.

Dest

The three destination bits (d1 d2 d3) determine where the result is stored. If d1 is 1, the result is stored in A. If d2 is 1, the result is stored in D. If d3 is 1, the result is stored in Memory[A]. Multiple bits may be one and the result will be forwarded to all of the places.

(I think it would be easier to remember these bits as da dd dm.)

So for example, lets look at the following instruction:

1  1  1  a c1 c2 c3 c4 c5 c6 da dd dm  0  0  0
1  1  1  0  0  0  0  0  1  0  1  1  0  0  0  0

This corresponds to the instruction for D+A and would store this in both the A and D registers.

Jump

j1 j2 j3
 0  0  0  null No jump
 0  0  1  JGT If out >  0 jump
 0  1  0  JEQ If out =  0 jump
 0  1  1  JGE If out >= 0 jump
 1  0  0  JLT If out <  0 jump
 1  0  1  JNE If out <= 0 jump
 1  1  0  JLE If out a  0 jump
 1  1  1  JMP Jump

j1 signifies we should jump if the result is less than zero. j2 signifies we should jump if the result is zero. j3 signifies we should jump if the result is greater than zero. As before, these can be combined.

Symbols

Predefined symbols refer to RAM addresses. The Virtual Registers, R0 through R15 refer to the first 16 words of memory. The Predefined Pointers, SP, LCL, ARG, THIS and THAT refer to the first 5 words of memory respectively. (These overlap with the virtual registers.) The I/O Pointers, SCREEN and KBD refer to addresses 0x4000 and 0x6000 which are where the memory maps for the screen and keyboard start.

Labels Symbols are on instructions to use as targets for GOTO commands.

Variable Symbols are any other symbol of the form Xxx and are assigned a unique memory address by the assembler.

Input/Output Handling

The screen is 512*256, black and white and is represented by 8K of memory.

Pixels are indexed from the top left corner and sorted into rows. 1 signifies black and 0 white.

The memory location 0x6000 contains the ASCII code of the currently pressed key.

Exercises

Multiply

    @R2
    M=0  // Put that zero into M[R2]

(LOOP)
    // if R0 == 0, goto END
    @R0
    D=M
    @END
    D;JEQ  // Jump to end if R0 == 0.

    // D = D-1
    D=D-1
    @R0
    M=D

    // R2 = R2 + R1
    @R1
    D=M
    @R2
    M=M+D

    @LOOP
    0;JMP

(END)

Fill

Turns the screen black when a button is held.