This refers you to my website, and the course page thereof.
Recorded last August, only change is that course meetings both start at 11 AM, for 1 1/2
hours - which we never exceeded last term.
We basically get up close and personal with the computer, its processor, Assembly language and C, the lowsest of the "high-level" languages. Software you will need.
Humans count by tens, because they have 10 digits (fingers). Computers don't! So they count by twos. The important ideas of arabic numbers, place value, and the number ZERO came to Europe from the arabs. I demonstrate conversion between binary and decimal numbers.
View this before doing Assignment 1Oops! What is 5 take away 7? We can use the leftmost bit of a number ( that will frequently be 0 ) to indicate sign (1 means negative) - The 2's complement system.
Page 15, the most useful table in the book. Don't leave for Mars without it!
How memory and processor work in a computer. The processor executes instructions, it has 32 registers, and an ALU (Arithmetic/Logic Unit.) I show the execution of a subtract instruction.
A simple program to calculate 2x+1. Using the MIPS simulators Mars and QtSpim. See how you can step through the program and watch how the registers change, and the programcounter goes up. See error messages apopear. In the next video, a recording of the January 19 class, you will see also how to test your programs on linux.ubishops.ca, and submit your final version,
View these before doing lab 1When we start doing labs, there is some software you might need to download. The first 2 are only for windows users. Linux and Mac-OS, use scp and ssh from a terminal window. The last 2 are for local copies of MIPS simulators, which you may need if your internet connection is slow.
Shahn Nadeau of ITS has made a video of how to download these. He also sent us the links to the sources he mentions.
Discussion about how the course works, assembly instructions and a Demonstration of how to write, and test an assigned program project. Mostly about operating system calls and use of registers. My program "worked" but mipsmark failed the second case. Why?
Starting with that annoying subtraction problem, that gaves a signed negative result, then a description of some math instructions. Insights into the RISC goal: to reduce the number of instructions, and the complexity of the processor. Multiply and divide use 2 special registers. Boolean algebra, truth tables, and how to construct an adder -- and then use it to subtract!
Control Flow. A while loop, with a way out. The branch and jump instructions change the PC register. The example counts the number of characters in a string. A string is an ARRAY of bytes, the end is marked by a binary zero. This can cause problems for input, as an unexpectedly long input may destroy other data. The file cchar.a is in examples/.
The same count characters in the C language. Syntex and comments explained. I write the program, compile it, and correct errors. The file cchar.c is likewise in examples/.
You asked for more C, so I did 2 versions of getting the sum of an array of integers. An array consists of an address, and you need to KNOW haw many numbers there are. I also suggested how to make meaningful comments. They should explain WHY you are doing something.
I have since typed in THREE versions that work, they are in /examples/.
You can get them all with the command (on linux) of
cp /home/COURSES/cs216/examples/sum* . (don't forget the dot)
sumave.c is last yea's and defines a function, then also does a floating point average of some chilly temperatures. Iam sure that now you can see why everyone's style is unique! There is always more than one way of doing anything.
The boolean instructions operate bitwise. There is a duality in boolean algebra rules. Observe the deMorgan laws, and the meaning of "Neither a borrower NOR a lender be." Also a compromise between assembly programmers and hardware designers, who want to reduce the instruction set. The compromise leads to "pseudo instructions" (marked with a dagger), that will be implemented by 1 or more hardware instructions. I also sketch the layout of a 2-register instruction, such as beq, which has a 16-bit immediate field that is added to the PC.
Develop the sum.c program into one that sums just the odd numbers in an array. The bitwise AND operation can decide if a number is odd or not. I do this test in C, and then do th same thing in MIPS. You might want to take a break betwen the two. All the code is in /home/COURSES/cs216/examples/
The nicely-formatted MIPS file is sum-odd-nice.a
I compile sum.c, talk about the steps in compiling, assembling and linking to produce an executable. I was then asked about numbers starting with 0, they are base 8. Please quit when you get bored.
How instruction is encoded by the assembler, ways of specifying addresses, and how to divide a program into main and functions. The important register conventions, including $ra for return address. Information about theMidterm.
How long is an array? How long is a string? For an array of integers (.word) we have to know. Strings are different. We have to go to the end, marked with \0. C has function strlen() for this. I write a MIPS function to loop until it is found. Functions are called with jal, and they return with the instruction jr $ra. man pages for C functions.
MIPS has lots of registers, but sharing them between independently written pieces of code -
functions, requires observing some conventions. A Last in, first out (LIFO) data structure, "The Stack"
is needed to enable funcionsto save and restore data, such as the contents of "saved" registers, $s0-$s7.
The top of the stack is located by the stack pointer, $sp, which is also a "saved register."
I apologize for changing 72 into 42 in my example.
$ra contains the return address. Any jal instruction will replace it, so it is necessary to
save $ra on the stack, and other values as well. This example calls a function swap to exchange two values in an array. The code is in examples/callswap.a
The next example, in Tuesday's video, is examples/writever.asm
I start out with a problem I can't solve: writing a number vertically. I only know to divide by ten, write the quotient vertically (which I still don't know how) if it is not 0, and then write the reminder and a newline. Being careful to follow ther register conventions, in the end it is solved. There were camera problems in the middle, so it is continued ....
Could you write another write vertical for me to call? Oh wait! Mine will do. Recursion! A corned of the screen is cut off by the good camera, sorry. Next time, say something! The code is in examples/writever.asm
The stack use in "code form a real comopiler" , page 103 is to be found in notes/p103-code.html, an animated page. As you move the mouse down, the stack changes.
I then talk about using stack to save registers, and introduce binary trees, which may be traversed recursively. The discussion continues in the class meeting, next...
It is here, more about stack, binary trees, and recursion.
More recursion, talk about traversing a binary tree, and more about recur1.a. I will prepare an alternate recur assignment, but have not yet done so. I talk about macros, and promised to do stack5.a, which I have now done, and it is available, the next video...
As promised during the class, I defined a macro named pop, and used it, in a file named stack5.am. To my astonishment, it actually worked in Mars.
To get it to work in spim and mipsmark, I used the command mapp stack5, which expands the macro, giving file stack5.a. I then used spim and mipsmark. See what happened. I paused the video only once, while I typed in the boring output statements.
For those of you who hate using the stack I describe the SPARC procssor register wheel, Dijkstra, who published the quicksort algorithm in 1960, when nobody knew hot to implement recursion, devised "a unique data structure with the property that the last item put in the nest is the first thing taken out," and implemented this strategy in assembly language. Dijkstra is also known for his claim, "Program testing can discover errors, but never prove their absence."
3 + 4 * 5 is ambiguous. Polish notation solves this problem, there are 2 forms,
prefix (suitable for recursive solutions)
postfix (ideal for using the stack)
Explaining thesyntax of grammar rules, and in particular prefix notation for arithmetic expressions. (No parentheses required). Prefix lends itself to recursive evaluation.
Postfix, on the other hand, can be evaluated using the stack.
Review of the course, in particular showing function for sum of an array, first in C and then in assembler.