• Special lab sessions to make up for any missed lab5s, including last Thursdays will be held Tuesday, 12/12 4:15-6:15 and 6:30-8:30.
• Venkatesh's Tues 12/12 noon office hours are rescheduled to Friday 11:00-1:00, in the ECL.

•  Solutions for the Summer 2000 MAL (tutorial) problems(text files):

 Question 2: Processing two arrays of integers
 Question 5 (computing an average)
• Room and Time for MAL problem tutorial:  Friday, 12/8 LC-20 12:20-2:20 PM.

•  Project 5 File copies on the Web.
•   Sample outputs for a JVM program that uses the bipush instruction, showing sign extension.
• Due date of project 5: Thursday, December 7 (not Tuesday).

• Project 4 input is always from standard input.  To indicate end-of-file when using the keyboard to supply standard input, key in
Control-d
 
•   Prof.Tom Anderson 's Quick Introduction to C++  Local Copy(.ps)    Local copy of examples(.tar)
• The handwritten modularization design drafts have been graded and placed in a folder in the ECL room HU-25, on the table with the box of old CSI333 handouts.  Any typewritten drafts will be returned later.

•  Web page of Resources for CSI333  including a tutorial on  RCS  from Cal. Poly.

•  Assembly Language Resourses for Labs, Projects and Coursework

Includes some required readings and material useful in the absence of Waldron's book.
•  Schedule of CSI333 and CSI201 Lab. Sessions, including which weeks the CSI333 sessions meet.(.ps)
•  Link to CSI201 home page http://www.cs.albany.edu/csi201. Information useful to all ECL users, especially transfer students new to Albany's CS Dept's ECL. Also, contains notes on C++ with material we expect you to know.

Information

The class newsgroup is sunya.class.csi333  It resides on usenet server cscnews.albany.edu  Click here for help on accessing USENET.

Some required readings or copies of handouts and lecture slides, and linked directly and indirectly from this page, will be Web documents in POSTSCRIPT and/or  ACROBAT format.  Inability to access Web based course material will NOT BE ACCEPTED as an excuse for course work lateness.  Click here for help with ACROBAT and POSTSCRIPT
 

• Course policies(.ps) (.pdf)
• Guidelines for lab exercises and programming assignments(.ps) (.pdf)

• Staff Lab and Office Hours
• Instructions for electronic submission of course work(.ps) (.pdf)


• Dr. John Waldron's (author of "Introduction to RISC Assembly Language Programming") home page
• Lin Jensen's MIPS Assembly Language Course Notes (Bishop's University, Quebec; link from Waldron's web site).
•  CS Dept. Educational Computing Laboratory Home Page
•  Telnet to the ECL (ecl.cs.albany.edu)

• Lecture 01 (9/5)(.ps) (.pdf)

(Coverage, what is architecture, variables are boxes, terms: digital, bit, representation. unsigned and signed 8 bit variable overflow demonstration and explanation, general effects of bitwise representation, alternatives to bits, radix ten example, binary example, counting to fifteen in binary, adding long numerals in decimal and binary, full-adder truth table, 4-bit adder built with full-adders, summation formula for the value of an unsigned bin. representation.
• Lecture 02 (9/7)(.ps) (.pdf)

Four kinds of "base conversion" problems depend on operations available on the converting agent (human versus computer) and direction of conversion (binary to decimal or decimal to binary). Hexadecimal (base 16). Bitwise logical operations in C/C++: first the single bit boolean operations AND, OR, EOR and NOT.  Then, the C/C++ bitwise integer operators.  Risk of confusion with C/C++ "logical" operations.
• Lecture 03 (9/12)(.ps) (.pdf)

MIPS assembly lang. programming, prep. Lab 1. (fetch-execute cycle, RISC instructions, C to assembly and other examples, variables, registers, addressable memory, pointers are addresses, how to use registers, how to use addressable memory. QUIZ 1 was given!)
Larus' Spim/Xspim Documentation(.ps) (.pdf)
• Lecture 04 (9/14)

Addressable memory, more small assembly language program examples, documention with (1) register use assignments and (2) invariant comments, counting MAL instructions, adding numbers using ADDIs,
• Lecture 05 (9/19) Lab Exercises 2(.ps)  (.pdf)

C/C++ shift operators, applications for bitwise ops, shifts and mask constants.  Mathematical significance of shifting.
• MIPS instruction formats (see Waldron, GM ch. 10, Patterson and Hennessy's book for CSI404, or

MIPS Corporation Web Site (view the manual there) http://www.mips.com
• MIPS Manual page for the ORI instruction(.ps)
C language parameter passing: always by value.  Illustration of a variable belonging to the caller and accessed (via a passed pointer) by the callee. More examples. Talk about C++ option to declare a reference parameter.  How Standard C printf works and how to use it. %d, %s, and %3s conversion specifications. Similar description for scanf.  Length and number of bytes required for storing C strings.
 
• Lecture 06 (9/21)

Unix file attributes: read, write, execute permissions for owner, group member and world.  Shells are command interpreters, executable files containing text function as input to a shell run.  How to write the simplest shell scripts.
Citation of Jon Bentley's "Programming Pearls" column in Dr. Dobbs Journal, Dec. 1999, on using a huge bit string to sort a huge set telephone numbers.
Correction of some typos in Project 1 specification:
• sample of hex and binary output of integer 62 is wrong
• printf("%#018x\n", value) should be printf("%#010x\n", value).  EITHER choice will be acceptable for project credit.

(Thanks to all students who alerted me to these errors!)
Buffering in the terminal device driver of the operating system and buffering in the iostream/stdio library, it's consequences when there are input format errors: Characters that haven't been interpreted remain in the iostream/stdio buffer.
How to use the read and write system call I/O functions.
Miscellaneous questions on Project 1.
 
• Lecture 07 (9/26)  Programming Project 2 Assigned with announcements(.ps)  (.pdf)

Lab exercise 2 on data structures is using assembly language to manipulate data structures.  You will see each data structure operation done by a series of machine instruction executions.  The time (spent by people waiting for the computation to finish) for one instruction is  "roughly" called one instruction cycle.  The model of constant time for executing each machine instruction is an excellent starting point for learning to understand how computers spend time on computations.  It is realistic for antique computers and current low end processors for small embedded applications. That is why we teach assembly language in CS curricula.  CS students will so eventually learn why (say) Java programs take so long to run and what to do about it.  The model is rough because modern computers have pipelines and caches which enable several machine instructions to be worked on simultaneously (at the same time).
• ASCII characters and Std. C character handling library.
• C char types, library functions to handle them.
• The C/C++ sizeof operator signifies a constant, eg when int X; sizeof(int) and sizeof(X) is 4 (on the ECL system).
• MIPS register conventions and SPIM simulated system calls, the hello.a example viewed through the simulator.
• Screen shot of xspim running hello.a program
• Screen shot of xspim running hello2.a program, shows how C strings are stored
•  Lecture 08 (9/28)
•  Input/Output  description of Project 2: Use of stack, etc.  Details are given in the assignment handout above.
• SPECIFICATION CHANGE: VERSION 3 POSTFIX OUTPUT MUST HAVE EACH OF THE POSTFIX EXPRESSON ELEMENTS (literals and operators) SEPARATED BY SINGLE BLANK CHARACTERS!!
• Context free grammar descriptions:
• Infix:

Infix ::= Literal | Infix Op Infix | ( Infix )
(This grammar is ambiguous; a practical grammar would express operator precedences.)
• Postfix:

Postfix ::= Literal | Postfix Postfix Op
(This grammar is NOT ambiguous.)
• Advantages of postfix:
• No () parentheses needed for any combination of operations.
• There's a left-to-right scanning procedure to "do" the calculation that only needs a stack for keeping intermediate results.
• Procedural Abstraction.
• Requirements for the output area elements.  Each element of the postfix output:
• Must be printable.
• Must support discriminating between literal and operator type.
• Must be able to indicate the identity of each operator, and the numeric value of each literal.
• Example of la, li, and lw MAL instructions.  Demo of address arithmetic of hello2.a example.
• Slides on MAL procedure linkage(.ps) (.pdf)

MAL procedure calling example 1(.ps)  (.pdf)
MAL procedure calling example 2(.ps)  (.pdf)
 
• Lecture 09 (10/3)

Discussion of modularization design for Project 2:
Input module, parser module
CHOICE of data type for passing the infix expression from the input to the parser.
Data Abstraction: datatype defined with the operations available on it.
Discussed for elements of infix and postfix expressions, which are literals and operators.
To make a stack:
1. Choose type (size) of each stack element.
2. Get a region of memory to hold the stack elements.
3. Use a memory word or a register to point to the top of the stack.
4. Implement pop, push, access top, and possibly overflow/underflow error detection
Picture showing stack entry space with entries with low addresses free, entries with higher addresses used, either memory pointer or register pointer pointing to the topmost USED entry.
Stack of operators (for parser)
Elements: +, -, *, /, (
Stack space:
STACKTOPLIM:  .space   40    #space for 40 1 byte entries
STACKBOTBYTE: .space   1     #dummy byte at the bottom of the stack
STACKPTR:     .word    STACKBOTBYTE  #pointer to top of stack
#initialized with address of bottom entry.
The evaluator's stack must have 32 bit words elements, to hold integer intermediate values
Stack space:
              .align    2    #align next allocated addr to multiple of 2^2=4
EVSTACKTOPLIM: .space   160   #40*4 bytes.
EVSTACKBOTWORD:.space   4     #dummy word at the bottom
EVSTACKPTR:    .word     EVSTACKBOTWORD
Project 2 requires TWO stacks of your own implementation: one for the parser and one for the evaluator, PLUS the use of the system stack for saving data that each function must protect from other functions.
Last 3 Slides on MAL procedure linkage(.ps) (.pdf)
Comments about argument passing alternatives:modern systems pass the first few arguments in registers because registers are faster.  Conventions must be followed for libraries to be interoperable.
MAL to TAL demo source
MAL to TAL demo annotated
Use of register $1 named $at for "assembler's temporary".   YOU must not code anything to touch it!
MIPS Manual page for the ORI instruction(.ps)
MIPS Manual page for the LUI instruction(.ps)
See Waldrom Ch. 6 or MIPS manual for MIPS instruction formats.
MIPS Corporation Web Site (view the manual there) http://www.mips.com

• Lecture 10 (10/5)
• Project 2 notes:
1. There are no  "decimal" numbers in this project!  Conversions between HEX and MIPS 32 bit unsigned binary are requested.  The arithmetic evaluation is done with MIPS integer instructions that operate on 32 bit binary numerals.
2. Only one version should be submitted.
3. Parnas wrote that the software building infrastructure (revision control system, build scripts, makefiles, etc) can be considered to be a module.  That module has NO functions that go into the completed software.
•  Case Study in MAL stack implementation(.txt)

Diagram of stack data structure, with each stack entry being a pointer into the char array plus a number.
Corresponding C++ declarations.
LI, LA, LW/LH/LB MAL instructions compared.
• Lecture 11 (10/10)

 Exam Guide(.ps)  (.pdf)
 Recursive reverser, storage areas(.ps)  (.pdf)
• Lecture 12 (10/12)  MIDTERM EXAM.  CLOSED BOOK, ONE SHEET OF NOTES, NO CALCULATORS/COMPUTERS.
• Lecture 13 (10/17)

Project 3 and Lab exercises 3 Assigned(.ps) (.pdf)
Storage Areas II(.ps)  (.pdf)
Dangling pointer dangers, C/C++ array name is a constant for the address of the first element (unlike Java which has arrays as "first class objects").
Automatic, static and free-store contrasted.
 Lecture 14 Slides Supporting Lab 3(.ps)  (.pdf)

• Lecture 14 (10/19)
Goal: Express or implement a modularized design as a collection of C/C++ source files.
Modular software design is independent of language.
Different programming environments (say Java) support expressing modularity in different ways.  E.g., Java does NOT use separate header and implementation files to separate interface from implementation.  Java interfaces are completely
specified in Java class files, which are similar to our object files.
 Lecture 14 Slides on preprocessor, Supporting Lab 3(.ps)  (.pdf)
What the macro processor does:  Pretty "dumb" text processing. It does no type checking.
Careful description of the #include directive.
The strread module example, with it's test driver.,
The strread module hides the secret of how big the input line length limit is.
C++ static keyword specifies a name is private to a file.
C++ extern keyword specifies that a name is DEFINED somewhere else.
Why the user AND the implementor files must BOTH #include the interface header file.
Steps of separate compilation and linking.
Reasons for multiple source files and separate compilations.
Motivation for make utility, meaning of DIRECT DEPENDENCY.
• Lecture 15 (10/24)
• Exams returned, comments:  Demonstration of competance in assembly language programming is required for passing this course.  To catch up, do lab exercise 2 now and then project 3.  Assembly language programming will be reexamined in the final exam.
• Recursive function: A function that either directly or indirectly calls itself.  Function calling and returning protocols enable functions to be recursive or not depending on what programmers want.
• Project 3 (pattern matching) demonstrated in class, features of increasing version numbers discussed.
•  Software building Dataflow diagram(.ps)  (.pdf)  (portrait,.ps)  (portrait,.pdf)
• Writing simple makefile rules to express direct dependencies, dependency relation from previous lecture.
• Lecture 16 (10/26)

Topic 05:  C Preprocessor
Use the g++/gcc -v option to observe the compiler driver's steps.
Explore /usr/include to see real examples of preprocessor usage, and prepare for job interviews!
General idea of macro processors which support DEFINING and REFERENCING of "abbreviations"
Example different from the C/C++ preprocessor: the Makefile language.
Example definition of a Make variable:    MYOBJS = main.o  strread.o  line.o
Example reference of a Make variable:    testone : $(MYOBJS)
More or less critical discussion of preprocessor usage and (better) alternatives.
Include guards (to prevent multiple definition errors.)
 Declarations, definitions and modularization rules(.ps)  (.pdf)
 The Make Algorithm(.txt)
• Safety: Guarantee that each file is rebuilt when any of its direct or indirect dependencies are changed, and build it from files that are up to date.
• Efficiency: Rebuild only those files whose direct or indirect dependencies changed.
• Lecture 17 (10/31)
• Materials for Lab Exercise 4 (Web page of links to text files)
• Finish declarations, definitions, modularization, make from Lecture 16.
• Finish slides on declarations, definitions and modularization(.ps)  (.pdf)
•  C Character Library(.ps)  (.pdf)
•  

• Lecture 18 (11/2)
• Project 4: C/C++ Identifier Cross Referencer(.ps)  (.pdf)
• Introductory discussion of the project.
•  The Make Algorithm(.txt)  and refinements of make

Default target, make variables (setting and referencing them), automatic variables, builtin rules, pattern rules.
• Begin: C string library(.ps)  (.pdf)
• Lecture 19 (11/7)

 Object Oriented Design For Cross Reference, String Table, Extendable Arrays(.ps)  (.pdf)
 State Machine Scanner(prelim)(.ps)  (.pdf)
• Lecture 20 (11/9)

Project 4 Announcements:
"Lite Version" 85(out of 100) points:
1. No backslash line continuations.
2. No multiline comments.
3. No float, long, hex, or unsigned numeric constants.
4. So, "line" = "logical line"
Revised due dates:
• Early Due Date: 5:00PM Nov 22. (5%  bonus)
• Thanksgiving grace period Nov.22-Nov.27.(no bonuses or penalties)
• Late turnin period Nov.27(9:00PM) to Nov 30(9:00)PM(10% off per day)
 Function Pointers in assembly language
Function Pointer Demo. (.C and .h C++ source files)
 Scanner Slides(for 333cxref project)(.ps)  (.pdf)
  Line class and tester program for it is in the ECL at ~csi333/Project4/SampleCode/line
 Sample Scanner for an assembler, listings given in class (Directory of design diagrams and subdirs of .C and .h C++ sources)
• Lecture 21 (11/14)

  Prof.Tom Anderson 's Quick Introduction to C++  Local Copy(.ps)    Local copy of examples(.tar)
 Improved (simplified) scanner demo code (Directory)at   ~csi333/Project4/SampleCode/scanner
Scanner slides of Lecture 20
 Scanner Sample code(2 per page .ps)  (.pdf)
• Lecture 22 (11/16)

Input/output is standard input/output.  Use line class from ~csi333/Project4/SampleCode/scanner
Talk about computer science problems distinguished from algorithms or programs to solve them.
Use a record for each identifier: The record records the spelling and the list of line number:position pairs for indentifier appearances.
Design choices: (1) Maintain the set of identifiers is sorted order with efficient search and insertion capability by means of a balanced search tree. (2) Maintain the set of identifiers as a dictionary so efficient search and insertion can be done first, then the set is sorted afterward.
 Sorting Slides (began with talk about records)(.ps)  (.pdf)
Balanced Search Trees
What's a tree.
What's a search tree: in-order traversal prints keys in sorted order.
Searching a search tree.
Balanced:  height <= C*log(N) when C is constant  and N is number of nodes.
2-3 trees: each node has 0, 2 or 3 children and all leaves are on the same level.
 Hash table and function from Generic System V spec.(.ps)
Explanation of hashing.
Full Generic System V ABI (ELF) Specification for contents of object files.(.pdf)
• Lecture 23 (11/21)  Sorting Slides(.ps)  (.pdf)
• Lecture 24 (11/28)
• Handout: Lab5(.ps)  (.pdf) ,  Project 5(.ps)  (.pdf) , Files Slides(.ps)  (.pdf) , Summer 2000 Final
• Java Virtual Machine, .class files, role of Java Compiler, introduction to project 5.
•  Reference to Java Virtual Machine Specification:http://java.sun.com/docs/books/vmspec/2nd-edition/html/VMSpecTOC.doc.html
• Files..needed for Project 5
• Lecture 25 (11/30)
• Object Oriented Programming Slides(.ps),  (.pdf)
•  Storage Area Review and Design (supplemental reference)
• Lecture 26 (12/5)
• Lecture 26 (12/5)

Using strcmp to test if a given option equals a constant string.
General Principles of simulation: World(or target) versus Simulation system, State and what it represents,
Simulation Cycle:
  Examine current State (and Input),
   choose output and new State depending on the current State and input
    set State to new State, continue cycle.
4 Alternatives for formatting files
Reading MIPS memory image using unformatted reads, gseeks, etc.
Java Language and Virtural Machine:
  Java Variables(.ps)  (.pdf)
 Java Class(.ps)    (.pdf)
Java Storage Areas(.ps)   (.pdf)
Java Method Invocation (.ps)   (.pdf)
How to do sign entension: Test if sign bit is 1 and if so, 0xFFFFFF00 | chardata
 
• Lecture 27 (12/7)

 C, C++ and a little on Java Strings(.ps)  (.pdf)
 
 
• Lecture 28 (12/12)

  Slides on mangled symbols, file formatting, etc.(.ps)  (.pdf)
Bit patterns quote from Patterson and Hennessy, some MIPS bit handling instructions, graphical reps of data types and pointers(from Stroustrup p.75, p87.

   C and other types, ENDIANESS(.ps)  (.pdf)

Negative integer lore(.ps) (.pdf)
 
(Bit fields and unions slides from Lecture 02 (9/7)(.ps) (.pdf)These are good to review for bit and number rep. material)
 

• Bottom of stack topics:(Higher priority new topics are pushed.  Here we show future lecture plans!)
• the hello2.a example, other examples.  The "True" MIPS machine language.(Covered in lab 1 exercise)

• Topic 02:  Number systems
• Topic 05:  C Preprocessor
• Topic 06:  "Final Remarks on C++": Scope and Extant Examples

• Algorithms to Convert Numbers to Radix Numerals(.ps) (.pdf)

• Project 1 and Lab Exercise 1(.ps) (.pdf)

Project 1 is due Sept. 25.
Exercise 1 is for the weeks of Sept. 11 and Sept. 18
There's no official lab exercise for the first class week, but the lab will be open if TA's are available for "trying it out." Newcomers to the lab are strongly encouraged to attend a lab session to get their ECL account password and learn to use the lab system.
•  Lab Exercises 2(.ps)  (.pdf)
•  Skeleton MAL program file ex2.a
•  Skeleton C Program File ex2.C
• Programming Project 2 Assigned with announcements(.ps)  (.pdf)
• Project 3  Assigned(.ps) (.pdf)
•  Lab 3 was based on this document(.ps)  (.pdf)
• Materials for Lab Exercise 4 (web page of linkst to text files)
•  Project 4: C/C++ Identifier Cross Referencer(.ps)  (.pdf)
• Project 5(.ps)  (.pdf)
•  Lab Exercise 5(.ps)  (.pdf)

Previous Years' Material(Fall 99 and before..), for those who "really" want to know..  

Exam Archives

• Last Year's Midterm
• Solutions to Last Year's Midterm

• Last Year's Final
• Solutions to Last Year's Final

• Midterm -- Fall 1998
• Solutions to Fall 1998 Midterm

This class meets on Tuesdays and Thursdays from 2:30 - 3:50 in LC 23.

What Was New

• Lab Exercise 2 is available (1 week before first Lab Ex. 2 session) See Projects and Assignments below.
• Midterm rescheduled from Oct 5 to Thursday, Oct. 12.  See Project 2 announcements and assignment!