venue : wipro gachibowli
resources : Patt Patel ppts
Session 5The LC-3 Program
types
Type of operands : Addresses, numbers, characters, logical data
Type of of operations:
A. Data Transfer: Move, load, store
B. Arithmetic: Add, Subtract
C. Logical: AND, OR, NOT
D. Transfer of Control: JUMP, RET, HALT
E. I/O: Input
F. Conversion: Convert
Addressing Modes
• Immediate
• Direct
• Indirect
• Register
• Register Indirect
• Displacement
• Stack
An addressing mode specifies how to calculate the effective memory address of an operand by using information held in registers and/or constants contained within a machine instruction or elsewhere.
Addressing Modes
• Immediate add reg1 reg2 constant reg1 := reg2 + constant;
MOV AX, 0005H
Operand is present in the register. Immediate addressing is used to declare constants or variables
Addressing modes
b. Direct
load reg, address
MOVE AX, [5000H]à effective address
Disadvantage is limited address space.
Addressing Modes
c. Indirect
MOV AX, [BX]
POINTERS
d. register
MOV BX, AX
e. register Indirect : MOV AX, [BX]
f. displacement : MOV AX, 50H[BX]
g. stack addressing:
LC-3 Overview: Instruction Set
Opcodes
• 15 opcodes
• Operate instructions: ADD, AND, NOT
• Data movement instructions: LD, LDI, LDR, LEA, ST, STR, STI
• Control instructions: BR, JSR/JSRR, JMP, RTI, TRAP
• some opcodes set/clear condition codes, based on result:
Ø N = negative, Z = zero, P = positive (> 0)
Data Types
• 16-bit 2’s complement integer
Addressing Modes
• How is the location of an operand specified?
• non-memory addresses: immediate, register
• memory addresses: PC-relative, indirect, base+offset
Operate Instructions
Only three operations: ADD, AND, NOT
Source and destination operands are registers
• These instructions do not reference memory.
• ADD and AND can use “immediate” mode,where one operand is hard-wired into the instruction.
Will show dataflow diagram with each instruction.
• illustrates when and where data moves to accomplish the desired operation
NOT (Register)
ADD/AND (Register)
ADD/AND (Immediate)
Data Movement Instructions
Load -- read data from memory to register
• LD: PC-relative mode
• LDR: base+offset mode
• LDI: indirect mode
Store -- write data from register to memory
• ST: PC-relative mode
• STR: base+offset mode
• STI: indirect mode
Load effective address -- compute address, save in register
• LEA: immediate mode
• does not access memory
LD (PC-Relative)
LDI (Indirect)
LDR (Base+Offset)
LEA (Immediate)
Control Instructions
Used to alter the sequence of instructions(by changing the Program Counter)
Conditional Branch
• branch is taken if a specified condition is true
Ø signed offset is added to PC to yield new PC
• else, the branch is not taken
Ø PC is not changed, points to the next sequential instruction
Unconditional Branch (or Jump)
• always changes the PC
TRAP
• changes PC to the address of an OS “service routine”
• routine will return control to the next instruction (after TRAP)
Condition Codes
LC-3 has three condition code registers: N -- negative Z -- zero P -- positive (greater than zero)
Set by any instruction that writes a value to a register(ADD, AND, NOT, LD, LDR, LDI, LEA)
Exactly one will be set at all times
• Based on the last instruction that altered a register
Branch Instruction
Branch specifies one or more condition codes.
If the set bit is specified, the branch is taken.
• PC-relative addressing:target address is made by adding signed offset (IR[8:0])to current PC.
• Note: PC has already been incremented by FETCH stage.
• Note: Target must be within 256 words of BR instruction.
If the branch is not taken,the next sequential instruction is executed.
BR (PC-Relative)
TRAP
Calls a service routine, identified by 8-bit “trap vector.”
When routine is done, PC is set to the instruction following TRAP.
(We’ll talk about how this works later.)
Another Example
Count the occurrences of a character in a file
• Program begins at location x3000
• Read character from keyboard
• Load each character from a “file”
Ø File is a sequence of memory locations
Ø Starting address of file is stored in the memory locationimmediately after the program
• If file character equals input character, increment counter
• End of file is indicated by a special ASCII value: EOT (x04)
• At the end, print the number of characters and halt(assume there will be less than 10 occurrences of the character)
A special character used to indicate the end of a sequenceis often called a sentinel.
• Useful when you don’t know ahead of time how many timesto execute a loop.
Flow Chart
Char Count in Assembly Language (1 of 3)
;
; Program to count occurrences of a character in a file.
; Character to be input from the keyboard.
; Result to be displayed on the monitor.
; Program only works if no more than 9 occurrences are found.
;
;
; Initialization
;
.ORIG x3000
AND R2, R2, #0 ; R2 is counter, initially 0
LD R3, PTR ; R3 is pointer to characters
GETC ; R0 gets character input
LDR R1, R3, #0 ; R1 gets first character
;
; Test character for end of file
;
TEST ADD R4, R1, #-4 ; Test for EOT (ASCII x04)
BRz OUTPUT ; If done, prepare the output
Char Count in Assembly Language (2 of 3)
;
; Test character for match. If a match, increment count.
;
NOT R1, R1
ADD R1, R1, R0 ; If match, R1 = xFFFF
NOT R1, R1 ; If match, R1 = x0000
BRnp GETCHAR ; If no match, do not increment
ADD R2, R2, #1
;
; Get next character from file.
;
GETCHAR ADD R3, R3, #1 ; Point to next character.
LDR R1, R3, #0 ; R1 gets next char to test
BRnzp TEST
;
; Output the count.
;
OUTPUT LD R0, ASCII ; Load the ASCII template
ADD R0, R0, R2 ; Covert binary count to ASCII
OUT ; ASCII code in R0 is displayed.
HALT ; Halt machine
Program (1 of 2)
Program (2 of 2)
Problem solving
Problem solving
clarifying description of the problem, analyzing causes, identifying alternatives, assessing each alternative, choosing one, implementing it, and evaluating whether the problem was solved or not.
•Define the problem
•Analyze the problem
•Isolate the task knowledge to solve the problem
•Choose the best problem solving technique
Problem solving
•What is the input
•What should be the output
•Procedure to convert the input to output
•Logic
•Understand the syntax of the tool being used
•The procedure should have a good control strategy
Problem solving techniques
Stepwise refinement
Starting from the requirements, at each step one constructs a more concrete description of the system and verifies it against the specification constructed in the previous step until one arrives at the implementation.
Programming is different from coding.
Programming is a sequence of design decisions concerning the decomposition of tasks into subtasks and of data into data structures.
Stepwise refinement
it is a software development technique that imposes a hierarchical structure on the design of the program. It starts out by defining the solution at the highest level of functionality and breaking it down further and further into small routines that can be easily documented and coded.
It is also called as top down programming
Techniques that impose a logical structure on the writing of a program. Large routines are broken down into smaller, modular routines .
constructs
• Sequential
• Conditional
• Iterative
Back to number system
Converting binary fraction to decimal fraction
1) 0.1101 =
= 1 x 2-1 + 1 x 2-2 + 0 x 2-3 + 1 X 2-4
=1/2 + ¼ + 0 + 1/16
= 0.8125
2) 1101.1010 = ?
NUMBER SYSTEM
CONVERTING DECIMAL FRACTION TO BINARY FRACTION
• 0.8125 =
FRACTION FR X 2 REM INTEGER
0.8125 1.625 0.625 1 MSB
0.625 1.25 0.25 1
0.25 0.50 0.50 0
0.50 1.00 0.00 1LSB
2) 0.635= ?
3) 12.625 = ?
4. Floating Point Numbers
Exponential Notation
• The following are equivalent representations of 1,234
Parts of a Floating Point Number
-0.9876 x 10-3
IEEE 754 Standard
• Most common standard for representing floating point numbers
• Single precision: 32 bits, consisting of...
• Sign bit (1 bit)
• Exponent (8 bits)
• Mantissa (23 bits)
• Double precision: 64 bits, consisting of…
• Sign bit (1 bit)
• Exponent (11 bits)
• Mantissa (52 bits)
Single Precision Format
Normalization
• The mantissa is normalized
• Has an implied decimal place on left
• Has an implied “1” on left of the decimal place
• E.g.,
• Mantissa ®
• Represents…
Excess Notation
• To include +ve and –ve exponents, “excess” notation is used
• Single precision: excess 127
• Double precision: excess 1023
• The value of the exponent stored is larger than the actual exponent
• E.g., excess 127,
• Exponent ®
• Represents…
Example
• Single precision
Hexadecimal
• It is convenient and common to represent the original floating point number in hexadecimal
• The preceding example…
Converting from Floating Point
• E.g., What decimal value is represented by the following 32-bit floating point number?
Converting to Floating Point
• E.g., Express 36.562510 as a 32-bit floating point number (in hexadecimal)
• Step 2
• Normalize
• Step 3
• Determine S, E, and M
• Step 4
• Put S, E, and M together to form 32-bit binary result
• Step 5
• Express in hexadecimal
Chapter 11Introduction toProgramming in C
C: A High-Level Language
Gives symbolic names to values
• don’t need to know which register or memory location
Provides abstraction of underlying hardware
• operations do not depend on instruction set
• example: can write “a = b * c”, even thoughLC-3 doesn’t have a multiply instruction
Provides expressiveness
• use meaningful symbols that convey meaning
• simple expressions for common control patterns (if-then-else)
Enhances code readability
Safeguards against bugs
• can enforce rules or conditions at compile-time or run-time
Compilation vs. Interpretation
Different ways of translating high-level language
Interpretation
• interpreter = program that executes program statements
• generally one line/command at a time
• limited processing
• easy to debug, make changes, view intermediate results
• languages: BASIC, LISP, Perl, Java, Matlab, C-shell
Compilation
• translates statements into machine language
Ø does not execute, but creates executable program
• performs optimization over multiple statements
• change requires recompilation
Ø can be harder to debug, since executed code may be different
• languages: C, C++, Fortran, Pascal
Compilation vs. Interpretation
Consider the following algorithm:
• Get W from the keyboard.
• X = W + W
• Y = X + X
• Z = Y + Y
• Print Z to screen.
If interpreting, how many arithmetic operations occur?
If compiling, we can analyze the entire program and possibly reduce the number of operations. Can we simplify the above algorithm to use a single arithmetic operation?
Compiling a C Program
Entire mechanism is usually called the “compiler”
Preprocessor
• macro substitution
• conditional compilation
• “source-level” transformations
Ø output is still C
Compiler
• generates object file
Ø machine instructions
Linker
• combine object files(including libraries)into executable image
Compiler
Source Code Analysis
• “front end”
• parses programs to identify its pieces
Ø variables, expressions, statements, functions, etc.
• depends on language (not on target machine)
Code Generation
• “back end”
• generates machine code from analyzed source
• may optimize machine code to make it run more efficiently
• very dependent on target machine
Symbol Table
• map between symbolic names and items
• like assembler, but more kinds of information
A Simple C Program
#include
#define STOP 0
/* Function: main */
/* Description: counts down from user input to STOP */
main()
{
/* variable declarations */
int counter; /* an integer to hold count values */
int startPoint; /* starting point for countdown */
/* prompt user for input */
printf("Enter a positive number: ");
scanf("%d", &startPoint); /* read into startPoint */
/* count down and print count */
for (counter=startPoint; counter >= STOP; counter--)
printf("%d\n", counter);
}
Preprocessor Directives
#include
• Before compiling, copy contents of header file (stdio.h)into source code.
• Header files typically contain descriptions of functions andvariables needed by the program.
Ø no restrictions -- could be any C source code
#define STOP 0
• Before compiling, replace all instances of the string"STOP" with the string "0"
• Called a macro
• Used for values that won't change during execution,but might change if the program is reused. (Must recompile.)
Comments
Begins with /* and ends with */
Can span multiple lines
Cannot have a comment within a comment
Comments are not recognized within a string
• example: "my/*don't print this*/string"would be printed as: my/*don't print this*/string
As before, use comments to help reader, not to confuseor to restate the obvious
main Function
Every C program must have a function called main().
This is the code that is executedwhen the program is run.
The code for the function lives within brackets:
main()
{
/* code goes here */
}
Variable Declarations
Variables are used as names for data items.
Each variable has a type,which tells the compiler how the data is to be interpreted(and how much space it needs, etc.).
int counter;
int startPoint;
int is a predefined integer type in C.
Input and Output
Variety of I/O functions in C Standard Library.
Must include
printf("%d\n", counter);
• String contains characters to print andformatting directions for variables.
• This call says to print the variable counter as a decimal integer, followed by a linefeed (\n).
scanf("%d", &startPoint);
• String contains formatting directions for looking at input.
• This call says to read a decimal integer and assign it to thevariable startPoint. (Don't worry about the & yet.)
More About Output
Can print arbitrary expressions, not just variables
printf("%d\n", startPoint - counter);
Print multiple expressions with a single statement
printf("%d %d\n", counter, startPoint - counter);
Different formatting options:
%d decimal integer
%x hexadecimal integer
%c ASCII character
%f floating-point number
Examples
This code:
printf("%d is a prime number.\n", 43);
printf("43 plus 59 in decimal is %d.\n", 43+59);
printf("43 plus 59 in hex is %x.\n", 43+59);
printf("43 plus 59 as a character is %c.\n", 43+59);
produces this output:
43 is a prime number.
43 + 59 in decimal is 102.
43 + 59 in hex is 66.
43 + 59 as a character is f.
Examples of Input
Many of the same formatting characters areavailable for user input.
scanf("%c", &nextChar);
• reads a single character and stores it in nextChar
scanf("%f", &radius);
• reads a floating point number and stores it in radius
scanf("%d %d", &length, &width);
• reads two decimal integers (separated by whitespace), stores the first one in length and the second in width
Must use ampersand (&) for variables being modified.(Explained in Chapter 16.)
Compiling and Linking
Various compilers available
• cc, gcc
• includes preprocessor, compiler, and linker
Lots and lots of options!
• level of optimization, debugging
• preprocessor, linker options
• intermediate files -- object (.o), assembler (.s), preprocessor (.i), etc.
Remaining Chapters
A more detailed look at many C features.
• Variables and declarations
• Operators
• Control Structures
• Functions
• Data Structures
• I/O
Emphasis on how C is converted to
LC-3 assembly language.
Also see C Reference in Appendix D.
Chapter 6Programming
Solving Problems using a Computer
Methodologies for creating computer programsthat perform a desired function.
Problem Solving
• How do we figure out what to tell the computer to do?
• Convert problem statement into algorithm,using stepwise refinement.
• Convert algorithm into LC-3 machine instructions.
Debugging
• How do we figure out why it didn’t work?
• Examining registers and memory, setting breakpoints, etc.
Stepwise Refinement
Also known as systematic decomposition.
Start with problem statement:
“We wish to count the number of occurrences of a characterin a file. The character in question is to be input fromthe keyboard; the result is to be displayed on the monitor.”
Decompose task into a few simpler subtasks.
Decompose each subtask into smaller subtasks,and these into even smaller subtasks, etc....until you get to the machine instruction level.
Problem Statement
Because problem statements are written in English,they are sometimes ambiguous and/or incomplete.
• Where is “file” located? How big is it, or how do I knowwhen I’ve reached the end?
• How should final count be printed? A decimal number?
• If the character is a letter, should I count bothupper-case and lower-case occurrences?
How do you resolve these issues?
• Ask the person who wants the problem solved, or
• Make a decision and document it.
Three Basic Constructs
There are three basic ways to decompose a task:
Sequential
Do Subtask 1 to completion,then do Subtask 2 to completion, etc.
Conditional
If condition is true, do Subtask 1;else, do Subtask 2.
Iterative
Do Subtask over and over, as long as the test condition is true.
Problem Solving Skills
Learn to convert problem statementinto step-by-step description of subtasks.
• Like a puzzle, or a “word problem” from grammar school math.
Ø What is the starting state of the system?
Ø What is the desired ending state?
Ø How do we move from one state to another?
• Recognize English words that correlate to three basic constructs:
Ø “do A then do B” Þ sequential
Ø “if G, then do H” Þ conditional
Ø “for each X, do Y” Þ iterative
Ø “do Z until W” Þ iterative
LC-3 Control Instructions
How do we use LC-3 instructions to encodethe three basic constructs?
Sequential
• Instructions naturally flow from one to the next,so no special instruction needed to gofrom one sequential subtask to the next.
Conditional and Iterative
• Create code that converts condition into N, Z, or P.Example: Condition: “Is R0 = R1?” Code: Subtract R1 from R0; if equal, Z bit will be set.
• Then use BR instruction to transfer control to the proper subtask.
Code for Conditional
Code for Iteration
Example: Counting Characters
Refining B
Refining B1
Refining B2 and B3
The Last Step: LC-3 Instructions
Use comments to separate into modules and to document your code.
Debugging
You’ve written your program and it doesn’t work.
Now what?
What do you do when you’re lost in a city?
• Drive around randomly and hope you find it?
PReturn to a known point and look at a map?
In debugging, the equivalent to looking at a mapis tracing your program.
• Examine the sequence of instructions being executed.
• Keep track of results being produced.
• Compare result from each instruction to the expected result.
Debugging Operations
Any debugging environment should provide means to:
• Display values in memory and registers.
• Deposit values in memory and registers.
• Execute instruction sequence in a program.
• Stop execution when desired.
Different programming levels offer different tools.
• High-level languages (C, Java, ...)usually have source-code debugging tools.
• For debugging at the machine instruction level:
Ø simulators
Ø operating system “monitor” tools
Ø in-circuit emulators (ICE)
– plug-in hardware replacements that give instruction-level control
LC-3 Simulator
Types of Errors
Syntax Errors
• You made a typing error that resulted in an illegal operation.
• Not usually an issue with machine language,because almost any bit pattern corresponds tosome legal instruction.
• In high-level languages, these are often caught during thetranslation from language to machine code.
Logic Errors
• Your program is legal, but wrong, so the results don’t match the problem statement.
• Trace the program to see what’s really happening anddetermine how to get the proper behavior.
Data Errors
• Input data is different than what you expected.
• Test the program with a wide variety of inputs.
Tracing the Program
Execute the program one piece at a time,examining register and memory to see results at each step.
Single-Stepping
• Execute one instruction at a time.
• Tedious, but useful to help you verify each step of your program.
Breakpoints
• Tell the simulator to stop executing when it reachesa specific instruction.
• Check overall results at specific points in the program.
Ø Lets you quickly execute sequences to get ahigh-level overview of the execution behavior.
Ø Quickly execute sequences that your believe are correct.
Watchpoints
• Tell the simulator to stop when a register or memory location changes or when it equals a specific value.
• Useful when you don’t know where or when a value is changed.
Example 1: Multiply
This program is supposed to multiply the two unsignedintegers in R4 and R5.
Debugging the Multiply Program
Example 2: Summing an Array of Numbers
This program is supposed to sum the numbersstored in 10 locations beginning with x3100,leaving the result in R1.
Debugging the Summing Program
Running the the data below yields R1 = x0024,but the sum should be x8135. What happened?
Example 3: Looking for a 5
This program is supposed to setR0=1 if there’s a 5 in one ten memory locations, starting at x3100.
Else, it should set R0 to 0.
Debugging the Fives Program
Running the program with a 5 in location x3108results in R0 = 0, not R0 = 1. What happened?
Example 4: Finding First 1 in a Word
This program is supposed to return (in R1) the bit position of the first 1 in a word. The address of the word is in location x3009 (just past the end of the program). If thereare no ones, R1 should be set to –1.
Debugging the First-One Program
Program works most of the time, but if data is zero,it never seems to HALT.
Debugging: Lessons Learned
Trace program to see what’s going on.
• Breakpoints, single-stepping
When tracing, make sure to notice what’s really happening, not what you think should happen.
• In summing program, it would be easy to not noticethat address x3107 was loaded instead of x3100.
Test your program using a variety of input data.
• In Examples 3 and 4, the program works for many data sets.
• Be sure to test extreme cases (all ones, no ones, ...).
