George M. Georgiou Brian Strader

111110001001110010010110100000101100100000011011000101000101100011111110110111101010001100101111000000010001001000011101000010 011000100111000101110000101100100010010100001110101110001010111100010111011001111001101001011010111000100011000011010111110000 000011001100010101001010010011010011010000110110100100111011011001011110001111001010011101001000101001010011101111001110010001 111001001110000110001101111101101101101111100000001100010000001001001010100111010111000010110100110001000011000100110111100101 100111101111010110101111101101010101110011111111100110101101101000000110101110101100100010101010111111101111010111100000110001 101000011011001101001000000010011000001101011010100000010010001111110111110001010110111010011100101000111111101111010111111111 001011000011100010001001110101110000100011111110000100011010101011001000001110110110001100001101101001110110011110000000011001 001000011000001001101011110100110001100000100100011011011100001011100000010011110000010001000010000100000100001001000000111101 000001110010100001100110101111011101100111011010011101010100110011100011101100011111001001111100101011000011011000001000001010001001011111011001111010101011100010010001101110011101010110011000111101110001111110101100111000111011101010010000001010110010 100011101011001101000101101100100110100001110010101110110101011110110100010110001011000000000100100111000011100011101011111111 110100011010110111001000101000101111001010111100111100111100011011110101100100110100010101010110011111010001000011110100111110 101011110101111111110101111010100111000000010001011000001101100101111010010110110100100010011111000100101000110110010011001100010010001001010111111011010011111001010000001100011100010110111100011101000001010100101000111001001011010000011111000001100011 011111011101011101110110010101000101111101011011000101110111010001100110001001011001001000000011110001110010110011110100100001

George M. Georgiou and Brian Strader

California State University, San Bernardino August 2005

CONTENTS

Contents

ii

List of Code Listings

v

List of Figures

vi

Programming in LC-3

vii

LC-3 Quick Reference Guide

x

1 ALU Operations

1?1

1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?1

1.1.1 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?1

1.1.2 Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?1

1.2 Instructions in LC-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?2

1.2.1 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?2

1.2.2 Bitwise AND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?2

1.2.3 Bitwise NOT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?2

1.2.4 Bitwise OR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?3

1.2.5 Loading and storing with LDR and STR . . . . . . . . . . . . . . . . . . . 1?3

1.3 How to determine whether an integer is even or odd . . . . . . . . . . . . . . . . . 1?3

1.4 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?3

1.5 What to turn in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?4

2 Arithmetic functions

2?1

2.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?1

2.1.1 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?1

2.1.2 Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?1

2.2 Operations in LC-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?2

2.2.1 Loading and storing with LDI and STI . . . . . . . . . . . . . . . . . . . . 2?2

2.2.2 Subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?2

2.2.3 Branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?3

2.2.4 Absolute value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?3

2.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?4

2.4 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?4

2.5 What to turn in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?4

Revision: 1.17, January 20, 2007

ii

CONTENTS

CONTENTS

3 Days of the week

3?1

3.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3?1

3.1.1 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3?1

3.1.2 Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3?1

3.2 The lab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3?1

3.2.1 Strings in LC-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3?1

3.2.2 How to output a string on the display . . . . . . . . . . . . . . . . . . . . 3?2

3.2.3 How to read an input value . . . . . . . . . . . . . . . . . . . . . . . . . . 3?2

3.2.4 Defining the days of the week . . . . . . . . . . . . . . . . . . . . . . . . 3?3

3.3 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3?4

3.4 What to turn in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3?4

4 Fibonacci Numbers

4?1

4.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4?1

4.1.1 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4?1

4.1.2 Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4?1

4.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4?1

4.3 Fibonacci Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4?1

4.4 Pseudo-code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4?2

4.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4?2

4.6 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4?3

4.7 What to turn in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4?3

5 Subroutines: multiplication, division, modulus

5?1

5.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5?1

5.1.1 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5?1

5.1.2 Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5?1

5.2 The program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5?1

5.2.1 Subroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5?1

5.2.2 Saving and restoring registers . . . . . . . . . . . . . . . . . . . . . . . . 5?2

5.2.3 Structure of the assembly program . . . . . . . . . . . . . . . . . . . . . . 5?2

5.2.4 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5?3

5.2.5 Division and modulus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5?3

5.3 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5?5

5.4 What to turn in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5?5

6 Faster Multiplication

6?1

6.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6?1

6.1.1 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6?1

6.1.2 Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6?1

6.2 The program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6?1

6.2.1 The shift-and-add algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 6?1

6.2.2 Examining a single bit in LC-3 . . . . . . . . . . . . . . . . . . . . . . . . 6?2

6.2.3 The MULT1 subroutine . . . . . . . . . . . . . . . . . . . . . . . . . . . 6?2

6.3 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6?2

6.4 What to turn in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6?2

7 Compute Day of the Week

7?1

7.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7?1

7.1.1 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7?1

7.1.2 Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7?1

7.1.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7?1

7.2 Zeller's formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7?2

7.3 Subroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7?2

7.3.1 Structure of program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7?2

iii

CONTENTS

CONTENTS

7.4 Testing: some example dates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7?3 7.5 What to turn in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7?3

8 Random Number Generator

8?1

8.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8?1

8.1.1 Inputs and Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8?1

8.2 Linear Congruential Random Number Generators . . . . . . . . . . . . . . . . . . 8?1

8.3 How to output numbers in decimal . . . . . . . . . . . . . . . . . . . . . . . . . . 8?2

8.3.1 A rudimentary stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8?3

8.4 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8?3

8.5 What to turn in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8?3

9 Recursive subroutines

9?1

9.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?1

9.1.1 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?1

9.1.2 Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?1

9.2 Recursive Subroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?1

9.2.1 The Fibonacci numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?1

9.2.2 Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?1

9.2.3 Catalan numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?2

9.2.4 The recursive square function. . . . . . . . . . . . . . . . . . . . . . . . . 9?2

9.3 Stack Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?3

9.4 The McCarthy 91 function: an example in LC-3 . . . . . . . . . . . . . . . . . . . 9?5

9.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?5

9.4.2 Some facts about the McCarthy 91 function . . . . . . . . . . . . . . . . . 9?5

9.4.3 Implementation of McCarthy 91 in LC-3 . . . . . . . . . . . . . . . . . . 9?5

9.5 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?7

9.6 What to turn in . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?7

iv

LIST OF CODE LISTINGS

1 "Hello World!" in LC-3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1.1 The ADD instruction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?2 1.2 The AND instruction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?3 1.3 The NOT instruction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?3 1.4 Implementing the OR operation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?3 1.5 Loading and storing examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1?4 1.6 Determining whether a number is even or odd. . . . . . . . . . . . . . . . . . . . . 1?4 2.1 Loading into a register. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?2 2.2 Storing a register. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?2 2.3 Subtraction: 5 - 3 = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?2 2.4 Condition bits are set. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?3 2.5 Branch if result was zero. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?3 2.6 Absolute value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2?4 3.1 Days of the week data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3?3 3.2 Display the day. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3?3 4.1 Pseudo-code for computing the Fibonacci number Fn iteratively . . . . . . . . . . 4?2 4.2 Pseudo-code for computing the largest n = N such that FN can be held in 16 bits . . 4?3 5.1 A subroutine for the function f (n) = 2n + 3. . . . . . . . . . . . . . . . . . . . . . 5?2 5.2 Saving and restoring registers R5 and R6. . . . . . . . . . . . . . . . . . . . . . . 5?3 5.3 General structure of assembly program. . . . . . . . . . . . . . . . . . . . . . . . 5?3 5.4 Pseudo-code for multiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5?4 5.5 Pseudo-code for integer division and modulus. . . . . . . . . . . . . . . . . . . . . 5?4 6.1 The shift-and-add multiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6?2 7.1 Structure of the program. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7?3 8.1 Generating 20 random numbers using Schrage's method. . . . . . . . . . . . . . . 8?2 8.2 Displaying a digit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8?2 8.3 Output a decimal number. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8?3 8.4 The code for the stack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8?4 9.1 The pseudo-code for the recursive version of the Fibonacci numbers function. . . . 9?2 9.2 The pseudo-code for the algorithm that implements recursive subroutines. . . . . . 9?4 9.3 The pseudo-code for the recursive McCarthy 91 function. . . . . . . . . . . . . . . 9?5 9.4 The pseudo-code for the McCarthy 91 recursive subroutine. . . . . . . . . . . . . . 9?7 9.5 The program that calls the McCarthy 91 subroutine. . . . . . . . . . . . . . . . . . 9?8 9.6 The stack subroutines PUSH and POP. . . . . . . . . . . . . . . . . . . . . . . . . 9?9 9.7 The McCarthy 91 subroutine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9?9

Revision: 1.17, January 20, 2007

v

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download