Coding braindump
About Posts Tools OSSU Tags
Coding braindump

Week 4 - Machine Language

Overview

Machine language or instruction set is a critically important aspect of building a computer system. This can in fact be done beofre building a computer by simulating this in java code for example and see what it needs to do. Three basic elements that machine language need to be able to do are:

  • How to specify the instructions, exact instructions/operations
  • What specific instructions to perform via the program counter for example
  • Where to find inputs to instructions and where to put the outputs, i.e. addressing

We will look at this in more detail in the next section. Obviously machine language is really handy for the ALU and the computer itself, but really terrible for humans. So a programmer will almost never program in machine langauge, but a high level prrogramming language. A compiler will then translate the high-level code into machine language. In some cases, people will need to interact directly with machine language, e.g. highly optimized code. In this course we will need to think about machine language. Howevver, reading sequences of bits is terrible, so we will use Mnemonics, e.g. ADD for 0100010 and R3 for 0011, R2 for 0010 etc. There are 2 ways of thinking about this: that Mnemonics only exist in our interpretation or ii) that we could allow a machine language programmer to write code in this so-called assembly language. In this course we will need to look at the second interpretation, because in week 6 we will actually build an assembler.

Elements

Machine Language can be quite important to understand. It specifies the supported operations, the conrol of the program etc. ML is usually done in correspondence with the hardware architecture There are some trade-offs when thinking about the type of machine language to use and which functions to implement in maching language: Silicon Area (need more complex circuits to do specific things really fast) vs. Time to complete instruction Machine Operations that should be implemented include:

  • Arithmetic Operations, add, subtract, etc.
  • Logical Operations, And, Or, etc.
  • Flow Control: goto X, if C then goto Y, …

There are differences between machine languages:

  • Richness of set of ops: divisions, bulk copy, etc.
  • Data types (width, floating point)

Arguably, the memory hierarchy is even more important than the set of operations given, because accessing a memory location is expensive: you need to supply a long address and getting the memory into CPU takes time. In order to solve this, we use a memory hierarchy, consisting of a set of memories that give good balance of trade off between size and access time. Every set of CPUs has a very small set of registers that are extremely fast and easy to addressL

  • Data Registers: basic arithmetics ADD R1, R2
  • Addresses: Specify a part of the bigger memory which we want to access: Store R1, @A

So how do we decide which op to work on next? We do this through addressing modes, these are different ways of telling the computer to work on some data.

  • Register: Add R1,R2 // R2 <- R2 + R1
  • Direct: Add R1, M[200] // Mem[200] <- Mem[200] + R1
  • Indirect: Add R1, @A // Mem[A] <- Mem[A] + R1
  • Immediate: Add 73, R1 // R1 <- R1 + 73

Usually we deal with I/O to the PC by piggybacking on to the memory:

  • E.g. by storing in registers some of the last information (e.g. mouse pointer location) on specific I/O. These will be taken up by drivers and software bits that know how to deal with these things.
  • Another important part of addressing is the flow control. Usually the CPU ticks off operations sequentially, but sometimes there needs to be a way to divert from the process
  • Sometimes we need to jump unconditionally, e.g. for a loop:
  • Sometimes we want to jump based on a condition: suppose we want to do sth on the absolute value of a number: only jump if sth is >0

Hack Computer

This is to give an overview over the platform of the hack computer. you have to understand both hardware and machine language to understand the computer. Specs:

  • 16 bit computer
  • Instruction memory consisting of 16-bit registers and
  • Data memory, also a sequence of 16-bit registers
  • CPU: mainly ALU
  • Instruction Bus/ data bus / address bus
  • Registers - the hack machine language recognizes 3 registers:
    • D holds a 16-bit value; i.e. a data value
    • A holds a 16-bit value; either a data value or an address value
    • M represents the 16-bit RAM register addressed by A
  • Syntax:
    • A instruction:
      • @value, where value is either a non-negative decimal constant or a symbol referring to such a constant
      • This sets the A register to value AND RAM[A] becomes the selected RAM register
      • Example: @21 sets the A register to 21 and RAM[21] becomes the selected RAM register
      • We use it to operate on memory and change values
    • C instruction:
      • dest = comp; jump
      • when we compute sth, we can store the result of the computation or use the computation to jump to another location.
      • computations can be a range of values, see video
      • destinations can be M, D MD, A, AM, AD or AMD, so we can store simultaneously in several registers.
    • Jump instructions are a bit hard to understand - they always compare the result of a computation to zero and then decide on whether to jump or not based on the comparison parameters (eq, gt, ge lt, etc.). They always compare in relation to zero, i.e. greater than zero, etc.

Hack Language Specs

We have a hardware consisting of a CPU, ROM and RAM. THe machine language consists of A and C instructions (see above). A program is a sequence of instructions batched together. You can write machine language using 2 different ways: using mnemonics or binary. Once it is translated into binary, you can load it into the CPU and execute. Here are the instructions for the respective A and C programs:

  • Semantics: set the A register to value
    • Symbolic syntax: @value
    • where value is either:
      • a non-negative decimal constant <= 32767 (2^15-1) or
      • a symbal referring to such a constant
    • Example: set A to 21
      • Symbolic: @21
      • Binary: 0000000000010101 (the first zero for specifying the A instruction, often called an op-code)
  • Semantics: C instruction
    • Symbolic: dest = comp; jump
    • Binary: 1 1 1 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3 (first bit = op code; 2nd&3rd bit not used, 4 - 10 bit = comp bit, 11 - 13 = dest, 14 - 16 = jump)

I/O

We use peripherals/IO devices to communicate with the computer. If you work in a high-level environment, you usually have several libraries to interact with IO devvices. But how do we interact with IO devices using only bits? The most important part is the screen memory map. The physical display is updated using the content of the memory map. Concerning the computer, the screen consists of a matrix of pixels which can be turned on or off. The memory map consists of 8k 16-bit words, which determines the number of pixels on the physical display.

Hack Programming

So on to the actual programming in our hack ML. Remember we have two instructions:

  • A instruction: is used to set the value of the A register to a certain value.
  • C instruction: used to do 3 different things:
    • Compute a certain expression
    • Store a computation in a location
    • Jump ahead and execute -> go-to.

This is a mnemonic language, so we fist have to translate via the assembler. After this: demonstration in the CPU emulator. There is the problem of NOP (Null Order Instruction Problem) Slide, where an attacker could insert malicious code after a program. We can end a program with an infinite loop, because computers never stand still. The language has several built-in symbols:

  • 16 virtual registers: R0 to R15, where the computer will replace the Register with the according number -> R4 -> 4. Why? Consider the following code:
    // RAM[5]=15
@15
D=A

@5
M=D
    In the first part, we use the A register as a ‘data’ register. We put the number 15 into A and then assign it to D. In the second pair of the instruction, we do sth. very different: we select the memory register number 5 (@5) and then assign it the value of D. This is troubling, because you use the same instruction for very different purposes and it is hard to tell what is what. So the recommendation is to use virtual registers to make the code more readable:
    // RAM[5]=15
@15
D=A

@R5
M=D
    This program will do the same thing, but is much easier to read. The R5 will be changed to 5. However, R5 and r5 are different things!
  • Other symbols:
    • SCREEN
    • KBD
    • another 6 we don’t use in this code

In this unit, we will talk more about high-level programming concepts, specifically:

  • branching: the ability to tell a computer what to do based on certain conditions. In Machine language, there is usually only one branching condition, namely ‘go to’. Consider the following example: there is a certain value in R0. Based on whether R0 is negative or positive, the value contained in it will get written to R1.

    @R0
D=M //D = RAM[0]

@8
D;JGT // if R0>0 goto 8

@R1
M=0 // RAM[1]=0
@10
0;JMP //end of program

@R1
M=1 // R1=1

@10
0;JMP

    What comes very handy to improve readability of the code are symbolic expressions. See the code below for an example:

    @R0
D=M

@POSITIVE
D;JGT

@R1
M=0
@END
0;JMP

(POSITIVE) //declaration of label -> here I will jump to by calling @POSITIVE above
@R1
M=1

(END)
@END
0;JMP

    The way these labels get handled is by translating to @n where n is the instruction number following the (LABEL) declaration. The labels declarations themselves do not get translated in the program code itself.

  • So let us talk about variables: in hack ML we have only one variable to worry about which can be represented using a single register. Check the following program:

        // flip.asm
    // flips values of RAM[0] and RAM[1]
    // temp = R1
    // R1 = R0
    // R0 = temp

    @R1
    D=M
    @temp
    M=D // temp = R1

    @R0
    D=M
    @R1
    M=D // R1=R0

    @temp
    D=M
    @R0
    M=D //R0=temp

(END)
    @END
    0;JMP

    So how does this work? Notice that we have this lable @temp without declaring it anywhere. What we are doing is to present the following pledge to the computer: ‘find some available memory unit (e.g. n) and use it to represent temp. From now on, every mention of @temp will actually refer to @n.

  • Iteration: once again a basic and very important concept in higher programming, this is not so easy to implement on a machine language basis. So let us start with some pseudocode to understand the concept a little better:

       // Computes RAM[1] = 1+2+...+RAM[0]
   n = R0
   i = 1
   sum = 0
LOOP:
   if i>n goto STOP
   sum = sum + i
   i = i + 1
   goto LOOP
STOP:
   R1 = sum

    This seems pretty basic and logically, however, how do we implement this in machine language where we have very few basic tenets to build on? Let us see:

      @R0 // select Register 0 and load it into memory
  D = M
  @n
  M = D // n = R0
  @i
  M = 1 // i = 1
  @sum
  M = 0 // sum = 0
(LOOP)

  @i
  D=M // load current counter
  @n
  D = D-M // deduct counter from n
  @STOP
  D;JGT // if i>n goto STOP

  @sum
  D=M //load sum into D
  @i
  D=D+M // add current number (i) to sum and save it in D
  @sum
  M=D // write the above (sum = sum + i) to @sum
  @i
  M=M+1 // i = i + 1
  @LOOP
  0;JMP

(STOP)
  @sum
  D=M
  @R1
  M=D // RAM[1] = sum
(END)

    Best Practice recommendations:

    • Write the program in pseudo code
    • write the program in assembly language
    • Test the program on paper using a variable-value trace table

The next unit will talk about pointers and input/output.

  • pointers: one thing with low-levvel programming is that the notion of array gets abstracted away while compiling. So on the hardware level, you really only know the starting address and the length of an array. So let us look at a bit of code:

    //  for (i=0; i<n; i++){
//      arr[i] = -1
//  }
// suppose arr = 100, n = 10

//arr = 100
@100
D = A
@arr
M=D

// n = 10
@10
D=A
@n
M=D

// initialize i = 0
@i
M=0

    So now that we have initialized everything, let us have a look at the logic behind running through the array operation:

    (LOOP)
  // if (i==n) goto END
  @i
  D=M
  @n
  D=D-M  // D = i - n
  @END
  D;JEQ // if D=0 (or i=n), then jump to the end

  // this is the heart of the loop: assigning the number -1 to the actual array
  // RAM[arr+1] = -1
  @arr // address arr and store its value in M
  D=M  // transfer value to D
  @i  // address the variable i and store its value in M
  A=D+M  // add up the arr value D and the value of i M (D+M) and put the result in the A    register. D+M store an address; this address is now assigned to A.
  M=-1 // by the time we call M = -1, the register affected is the register addressed by A.

  // i++
  @i
  M = M+1

  @LOOP
  0;JMP

(END)
  @END
  0;JMP

    So the new bit of processing here is the A register.

    • Variables that store memory addresses like arr and i are called pointers
    • Hack pointer logic: whenever we have to access memory with a pointer, we need sth. like A=M

  • input/output: remember that we have the screen memory map and the keyboard which correspond to some addresses in the memory. The labels @SCREEN and @KBD refer to the base addresses of the screen and keyboard map respectively.

    • Working with the screen
      • example: draw a rectangle at the upper left corner of the screen, 16 pixels wide and RAM[0] pixels long.
      • So first we start with the pseudo code of writing to the screen memory map; let us start:
        // for (i=0; i<n; i==){
//     draw 16 black pixels at the beginning of row i
// }

addr = SCREEN
n = RAM[0]
i = 0

LOOP:
  i i>n goto END
  RAM[addr] = -1 //11111111111111
  // advances to next row
  addr = addr + 32
  i = i + 1
  goto LOOP

END:
  goto END
      • then we have to translate the pseudo code into actual machine code, which should not be too complicated by now.
          //draw a filled rectangle at the left corner with width 16 px and height of RAM[0] pixels

  @SCREEN
  D=A
  @addr
  M=D // addr = 16384 (screen base address)

  @0
  D=M
  @n
  M=D // n = RAM[0]

  @i
  M=0 // i == 0

(LOOP)
  @i
  D=M
  @n
  D=D-M
  @END
  D;JGT // if i>n goto END

  @addr
  A=M
  M=-1 // RAM[addr]=11111111111111

  @i
  M=M+1 // i = i+1
  @32
  D=A
  @addr
  M=D+M // addr = addr + 32
  @LOOP
  0;JMP // goto LOOP

(END)
  @END // program's end
  0;JMP // infinite loop
    • Working with the keyboard: the standard address for keyboard is 24576. So as a programmer we have to write code that reads the content of 24576 or (addr KBD) and determine the scan code of the key pressed. if 0, no key is pressed.
    • This is very low-level programming. Usually writing code at this level is very tedious and is usually done in higher level programming languages and then using a compiler.

Project 4

Overview: Next week we will combine all chips together into the hack computer. So this project focuses on:

  • low-level programming
  • hack assembly language
  • hack hardware

For course two there will be avery efficient algorithm for multiplication, but we are not expected to do this in our implementation. Just keep it in mind.

  • [2/2] Project 4:
    • Write a simple algebraic program: Mult - a program performing R2 = R0*R1. Recall that the Hack language does not have multiplication, instead you will have to use a loop and addition.

      • Solution

        // Multiplies R0 and R1 and stores the result in R2.
// (R0, R1, R2 refer to RAM[0], RAM[1], and RAM[2], respectively.)
//
// This program only needs to handle arguments that satisfy
// R0 >= 0, R1 >= 0, and R0*R1 < 32768.
// Pseudocode:
// Set R2 to 0
// Set i to 0
//   While i < R1
//   R2 = R2 + R0
//   i++


  @R2
  M=0 // set R2 to 0
  @i
  M=0 // set i to 0 (i will get initialized at Register 16)

(LOOP)
  // This is the logic to compare the value of the counter 'i'
  // to one of the factors in the multiplication (R0)
  @i
  D=M // put the value of 'i' (0 at the beginning) in D
  @R0
  D=D-M // D = i - R0
  @END
  D;JGE // if i>=n, then end loop

  // This is doing the actual multiplication
  @R1
  D=M // save content of R1 to D
  @R2
  M = M + D // add R1 to R2 for as long as the loop runs
  @i
  M = M + 1
  @LOOP
  0;JMP // else continue loop

(END)
  @END
  0;JMP

        I always find it relatively hard to understand this low-level code, so let’s walk through it. First we set R2 to zero, then we do the same for i. When we do this for i, it will get initialized as a label to Register 16.

        Then we start the loop. The first block here compares the value of i against to R0 and end the loop if i>R0.

        If not, we go into the actual calculation: First select R1 and save the contents of it ot D. Then add this to R2 and increase the counter i. Jump back to the beginning of the loop.

    • Simple interactive program: FILL - a program that blackens the whole screen as soon as you press any key and whitens it as soon as you lift the finger. First, you will have to listen to the keyboard. Then write some code that fills the entire screen memory with white or black pixels. Addressing the memory requires working with pointers.

      • Solution:

        // Runs an infinite loop that listens to the keyboard input.
// When a key is pressed (any key), the program blackens the screen,
// i.e. writes "black" in every pixel;
// the screen should remain fully black as long as the key is pressed.
// When no key is pressed, the program clears the screen, i.e. writes
// "white" in every pixel;
// the screen should remain fully clear as long as no key is pressed.
// Put your code here.
// Pseudocode:
// Initialize anything?
// (LOOP)
  // read keyboard
  // if 0
  // check if everything was already white:
  //  yes:keep it
  //  no: change it
  // if not 0
  // check if screen is black
  //   yes: keep it
  //   no: change it

  // initialization
  @status // memory location for holding the last drawn screen state
          // -1 for black, 0 for white
  M=-1  // set status to black=0xFFFF
  D=0 // Save 0 to D. Argument - what to set screen bits to
  @SETSCREEN //write screen
  0;JMP

(LOOP)
  @KBD //check keyboard input
  D=M // D = current KBD input
  @SETSCREEN
  D;JEQ // if no key, go to (SETSCREEN)
  D=-1 // if a key has been pressed, set screen to all 1 bits (black)

(SETSCREEN)
  @arg
  M=D // set the current status (lines 31 and 39) to arg, 0 to start with
  @status
  D=D-M // D = status_of_current_run - status_of_previous_run -> compare status against each other; 0 if equal
  @LOOP
  D;JEQ //if status_of_current_run == status_of_previous_run, start from (LOOP)

  // this only executes if @status != equal
  @arg
  D=M // load current status
  @status
  M=D // save current status

  @screen
  D=A //D = Screen address
  @8192 // number of registers in screen: 8191
  D=D+A //D=Byte just past last screen address
  @i
  M=D // i = Byte just past last screen address

(SETLOOP)
  @i
  D=M-1
  M=D // i = i-1
  @LOOP
  D;JLT // if i<0 goto LOOP

  @status
  D=M
  @i
  A=M //indirect
  M=D // M[current screen address]=status
  @SETLOOP
  0;JMP
        • Look at the pseudocode: what we have to do is check the keyboard and then paint the screen black as long as a key is pressed. However, there is an issue with performance: if the screen is already blac, we do not want to paint it black again - this would be a waste of resources.
        • So first comes the section where we initialize: create a label for the status and set the status to -1. Then put white pixels in our D register and jump to SETSCREEN to write white pixels first on our screen.
        • Next comes the main loop. This checks the keyboard input @KBD; we assign this keyboard input to D. If D is 0 (i.e. no keyboard input), then the condition D;JEQ takes hold, we jump to SETSCREEN with 0 in D. If the condition is not true, i.e. there is a keyboard input, then assign -1 to D (meaning black).
        • Then we run into the SETSCREEN Label, where we decide wehether to paint the screen or not. First we store the desired state (0 or -1) into arg. Then we retrieve the current status and compare it to the desired status (still in D): D=D-M. Then - if the comparison shows that the current and the desired state are the same, i.e. the result is zero - we jump to the beginning of the loop again (because D;JEQ holds).
        • If the condition does not hold, we move on. First retrieve the arg, then assign to @status. Then jump to the screen address and prepare to write all screen memory from address 24575 down to 16384.
        • Then move into the actual loop to paint the screen: @i is the pixel just past the screen end, so we start with this. We take this address and subtract 1. Only if we are finished (i<0), go back to the loop again.
        • If not go on to retrieve the current status (which is now the desired one) and save it to D. Then address @i which is the current screen address and paint it the desired state. Repeat this until the whole screen is black.
  • Some general remarks: programs will reside in standard text files with the .asm ending. You must use symbolic variables and labels. Use sensible variable and label names. variables: lower-case; Labels: upper-case