1 Welcome Aboard

1.1 What We Will Tryto Do

1.2 How We Will Get There

1.3 Two Recurring Themes

1.3.1 The Notion of Abstraction

1.3.2 Hardware versus Software

1.4 A Computer System

1.5 Two Very Important Ideas

1.6 Computers as Universal Computational Devices

1.7 How Do We Get the Electrons to Do the Work？

1.7.1 The Statement of the Problem

1.7.2 The Algorithm

1.7.3 The Program

1.7.4 The ISA

1.7.5 The Microarchitecture

1.7.6 The Logic Circuit

1.7.7 The Devices

1.7.8 Putting It Together

Exercises

2 Bits， Data Types， and Operations

2.1 Bits and Data Types

2.1.1 The Bit as the Unit of Information

2.1.2 Data Types

2.2 Integer Data Types

2.2.1 Unsigned Integers

2.2.2 Signed Integers

2.3 2’s Complement Integers

2.4 Binary-Decimal Conversion

2.4.1 Binary to Decimal Conversion

2.4.2 Decimal to Binary Conversion

2.5 Operations on Bits-Part Ⅰ：Arithmetic

2.5.1 Addition and Subtraction

2.5.2 Sign-Extension

2.5.3 Overflow

2.6 Operations on Bits-Part Ⅱ：Logical Operations

2.6.1 The AND Function

2.6.2 The OR Function

2.6.3 The NOT Function

2.6.4 The Exclusive-OR Function

2.7 Other Representations

2.7.1 The Bit Vector

2.7.2 Floating Point Data Type

2.7.3 ASCII Codes

2.7.4 Hexadecimal Notation

Exercises

3 Digital Logic Structures

3.1 The Transistor

3.2 Logic Gates

3.2.1 The NOT Gate （Inverter）

3.2.2 OR and NOR Gates

3.2.3 AND and NAND Gates

3.2.4 DeMorgan’s Law

3.2.5 Larger Gates

3.3 Combinational Logic Circuits

3.3.1 Decoder

3.3.2 Mux

3.3.3 Full Adder

3.3.4 The Programmable Logic Array（PLA）

3.3.5 Logical Completeness

3.4 Basic Storage Elements

3.4.1 The R-S Latch

3.4.2 The Gated D Latch

3.4.3 A Register

3.5 The Concept of Memory

3.5.1 Address Space

3.5.2 Addressability

3.5.3 A 2 2-by-3-Bit Memory

3.6 Sequential Logic Circuits

3.6.1 A Simple Example：The Combination Lock

3.6.2 The Concept of State

3.6.3 Finite State Machines

3.6.4 An Example：The Complete Implementation of a Finite State Machine

3.7 The Data Path of the LC-3

Exercises

4 The von Neumann Model

4.1 Basic Components

4.1.1 Memory

4.1.2 Processing Unit

4.1.3 Input and Output

4.1.4 Control Unit

4.2 The LC-3：An Example von Neumann Machine

4.3 Instruction Processing

4.3.1 The Instruction

4.3.2 The Instruction Cycle

4.4 Changing the Sequence of Execution

4.4.1 Control of the Instruction Cycle

4.5 Stopping the Computer

Exercises

5 The LC-3

5.1 The ISA：Overview

5.1.1 Memory Organization

5.1.2 Registers

5.1.3 The Instruction Set

5.1.4 Opcodes

5.1.5 Data Types

5.1.6 Addressing Modes

5.1.7 Condition Codes

5.2 Operate Instructions

5.3 Data Movement Instructions

5.3.1 PC-Relative Mode

5.3.2 Indirect Mode

5.3.3 Base+offset Mode

5.3.4 Immediate Mode

5.3.5 An Example

5.4 Control Instructions

5.4.1 Conditional Branches

5.4.2 An Example

5.4.3 Two Methods for Loop Control

5.4.4 Example： Adding a Column of Numbers Using a Sentinel

5.4.5 The JMP Instruction

5.4.6 The TRAP Instruction

5.5 Another Example： Counting Occurrences of a Character

5.6 The Data Path Revisited

5.6.1 Basic Components of the Data Path

5.6.2 The Instruction Cycle

Exercises

6 Programming

6.1 Problem Solving

6.1.1 Systematic Decomposition

6.1.2 The Three Constructs：Sequential，Conditional，Iterative

6.1.3 LC-3 Control Instructions to Implement the Three Constructs

6.1.4 The Character Count Example from Chapter 5，Revisited

6.2 Debugging

6.2.1 Debugging Operations

6.2.2 Examples： Use of the Interactive Debugger

Exercises

7 Assembly Language

7.1 Assembly Language Programming-Moving Up a Level

7.2 An Assembly Language Program

7.2.1 Instructions

7.2.2 Pseudo-ops （Assembler Directives）

7.2.3 Example： The Character Count Example of Section 5.5，Revisited

7.3 The Assembly Process

7.3.1 Introduction

7.3.2 A Two-Pass Process

7.3.3 The First Pass： Creating the Symbol Table

7.3.4 The Second Pass： Generating the Machine Language Program

7.4 Beyond the Assembly of a Single Assembly Language Program

7.4.1 The Executable Image

7.4.2 More than One Object File

Exercises

8 I/O

8.1 I/O Basics

8.1.1 Device Registers

8.1.2 Memory-Mapped I/O versus Special Input/Output Instructions

8.1.3 Asynchronous versus Synchronous

8.1.4 Interrupt-Driven versus Palling

8.2 Input from the Keyboard

8.2.1 Basic Input Registers （the KBDR and the KBSR）

8.2.2 The Basic Input Service Routine

8.2.3 Implementation of Memory-Mapped Input

8.3 Output to the Monitor

8.3.1 Basic Output Registers （the DDR and the DSR）

8.3.2 The Basic Output Service Routine

8.3.3 Implementation of Memory-Mapped Output

8.3.4 Example： Keyboard Echo

8.4 A More Sophisticated Input Routine

8.5 Interrupt-Driven I/O

8.5.1 What Is Interrupt-Driven I/O？

8.5.2 Why Have Interrupt-Driven I/O？

8.5.3 Generation of the Interrupt Signal

8.6 Implementation of Memory-Mapped I/O，Revisited

Exercises

9 TRAP Routines and Subroutines

9.1 LC-3 TRAP Routines

9.1.1 Introduction

9.1.2 The TRAP Mechanism

9.1.3 The TRAP Instruction

9.1.4 The Complete Mechanism

9.1.5 TRAP Routines for Handling I/O

9.1.6 TRAP Routine for Halting the Computer

9.1.7 Saving and Restoring Registers

9.2 Subroutines

9.2.1 The Call/Return Mechanism

9.2.2 The JSR（R） Instruction

9.2.3 The TRAP Routine for Character Input， Revisited

9.2.4 PUTS： Writing a Character String to the Monitor

9.2.5 Library Routines

Exercises

10 And， Finally…The Stack

10.1 The Stack：Its Basic Structure

10.1.1 The Stack-An Abstract Data Type

10.1.2 Two Example Implementations

10.1.3 Implementation in Memory

10.1.4 The Complete Picture

10.2 Interrupt-Driven I/O （Part 2）

10.2.1 Initiate and Service the Interrupt

10.2.2 Return from the Interrupt

10.2.3 An Example

10.3 Arithmetic Using a Stack

10.3.1 The Stack as Tempora Storage

10.3.2 An Example

10.3.3 OpAdd， OpMult， and OpNeg

10.4 Data Type Conversion

10.4.1 Example： The Bogus Program：2+3=e

10.4.2 ASCII to Binary

10.4.3 Binary to ASCII

10.5 Our Final Example： The Calculator

Exercises

11 Introduction to Programmingin C

11.1 Our Objective

11.2 Bridging the Gap

11.3 Translating High-Level Language Programs

11.3.1 Interpretation

11.3.2 Compilation

11.3.3 Pros and Cons

11.4 The C Programming Language

11.4.1 The C Compiler

11.5 A Simple Example

11.5.1 The Function main

11.5.2 Formatting， Comments，and Style

11.5.3 The C Preprocessor

11.5.4 Input and Output

11.6 Summary

Exercises

12 Variables and Operators

12.1 Introduction

12.2 Variables

12.2.1 Three Basic Data Types：int，char，double

12.2.2 Choosing Identifiers

12.2.3 Scope：Local versus Global

12.2.4 More Examples

12.3 Operators

12.3.1 Expressions and Statements

12.3.2 The Assignment Operator

12.3.3 Arithmetic Operators

12.3.4 Order of Evaluation

12.3.5 Bitwise Operators

12.3.6 Relational Operators

12.3.7 Logical Operators

12.3.8 Increment /Decrement Operators

12.3.9 Expressions with Multiple Operators

12.4 Problem Solving Using Operators

12.5 Tying it All Together

12.5.1 Symbol Table

12.5.2 Allocating Space for Variables

12.5.3 A Comprehensive Example

12.6 Additional Topics

12.6.1 Variations of the Three Basic Types

12.6.2 Literals，Constants，and Symbolic Values

12.6.3 Storage Class

12.6.4 Additional C Operators

12.7 Summary

Exercises

13 Control Structures

13.1 Introduction

13.2 Conditional Constructs

13.2.1 The if Statement

13.2.2 The if-else Statement

13.3 Iteration Constructs

13.3.1 The while Statement

13.3.2 The for Statement

13.3.3 The do-while Statement

13.4 Problem Solving Using Control Structures

13.4.1 Problem 1：Approximating the Value of π

13.4.2 Problem 2：Finding Prime Numbers Less than 100

13.4.3 Problem 3：Analyzing an E-mail Address

13.5 Additional C Control Structures

13.5.1 The switch Statement

13.5.2 The break and continue Statements

13.5.3 An Example：Simple Calculator

13.6 Summary

Exercises

14 Functions

14.1 Introduction

14.2 Functions in C

14.2.1 A Function with a Parameter

14.2.2 Example： Area of a Ring

14.3 Implementing Functions in C

14.3.1 Run-Time Stack

14.3.2 Getting It All to Work

14.3.3 Tying It All Together

14.4 Problem Solving Using Functions

14.4.1 Problem 1：Case Conversion

14.4.2 Problem 2：Pythagorean Triples

14.5 Summary

Exercises

15 Testing and Debugging

15.1 Introduction

15.2 Types of Errors

15.2.1 Syntactic Errors

15.2.2 Semantic Errors

15.2.3 Algorithmic Errors

15.3 Testing

15.3.1 Black-Box Testing

15.3.2 White-Box Testing

15.4 Debugging

15.4.1 Ad Hoc Techniques

15.4.2 Source-Level Debuggers

15.5 Programming for Correctness

15.5.1 Nailing Down the Specification

15.5.2 Modular Design

15.5.3 Defensive Programming

15.6 Summary

Exercises

16 Pointers and Arrays

16.1 Introduction

16.2 Pointers

16.2.1 Declaring Polnter Variables

16.2.2 Pointer Operators

16.2.3 Passing a Reference Using Pointers

16.2.4 Null Pointers

16.2.5 Demystifying the Syntax

16.2.6 An Example Problem Involving Pointers

16.3 Arrays

16.3.1 Declaring and Using Arrays

16.3.2 Examples Using Arrays

16.3.3 Arrays as Parameters

16.3.4 Strings in C

16.3.5 The Relationship Between Arrays and Pointers in C

16.3.6 Problem Solving：Insertion Sort

16.3.7 Common Pitfalls with Arrays in C

16.4 Summary

Exercises

17 Recursion

17.1 Introduction

17.2 What Is Recursion？

17.3 Recursion versus Iteration

17.4 Towers of Hanoi

17.5 Fibonacci Numbers

17.6 Binary Search

17.7 Integer to ASCII

17.8 Summary

Exercises

18 I/O i n C

18.1 Introduction

18.2 The C Standard Library

18.3 I/O，One Character at a Time

18.3.1 I/O Streams

18.3.2 putchar

18.3.3 getchar

18.3.4 Buffered I/O

18.4 Formatted I/O

18.4.1 printf

18.4.2 scanf

18.4.3 Variable Argument Lists

18.5 I/O from Files

18.6 Summary

Exercises

19 Data Structures

19.1 Introduction

19.2 Structures

19.2.1 typedef

19.2.2 Implementing Structures in C

19.3 Arrays of Structures

19.4 Dynamic Memory Allocation

19.4.1 Dynamically Sized Arrays

19.5 Linked Lists

19.5.1 An Example

19.6 Summary

Exercises

A The LC-3 ISA

A.1 Overview

A.2 Notation

A.3 The Instruction Set

A.4 Interrupt and Exception Processing

A.4.1 Interrupts

A.4.2 Exceptions

B From LC-3 to x86

B.1 LC-3 Features and Corresponding x86Features

B.1.1 Instruction Set

B.1.2 Memory

B.1.3 Internal State

B.2 The Format and Specification of x86Instructions

B.2.1 Prefix

B.2.2 Opcode

B.2.3 ModR/M Byte

B.2.4 SIB Byte

B.2.5 Displacement

B.2.6 Immediate

B.3 An Example

C The Microarchitecture of the LC-3

C.1 Overview

C.2 The State Machine

C.3 The Data Path

C.4 The Control Structure

C.5 Memory-Mapped I/O

C.6 Interrupt and Exception Control

C.6.1 Initiating an Interrupt

C.6.2 Returning from an Interrupt，RTI

C.6.3 The Illegal Opcode Exception

C.7 Control Store

D The C Programming Language

D.1 Overview

D.2 C Conventions

D.2.1 Source Files

D.2.2 Header Files

D.2.3 Comments

D.2.4 Literals

D.2.5 Formatting

D.2.6 Keywords

D.3 Types

D.3.1 Basic Data Types

D.3.2 Type Qualifiers

D.3.3 Storage Class

D.3.4 Derived Types

D.3.5 typedef

D.4 Declarations

D.4.1 Variable Declarations

D.4.2 Function Declarations

D.5 Operators

D.5.1 Assignment Operators

D.5.2 Arithmetic Operators

D.5.3 Bit-wise Operators

D.5.4 Logical Operators

D.5.5 Relational Operators

D.5.6 Increment/Decrement Operators

D.5.7 Conditional Expression

D.5.8 Pointer，Array，and Structure Operators

D.5.9 sizeof

D.5.10 Order of Evaluation

D.5.11 Type Conversions

D.6 Expressions and Statements

D.6.1 Expressions

D.6.2 Statements

D.7 Control

D.7.1 If

D.7.2 If-else

D.7.3 Switch

D.7.4 While

D.7.5 For

D.7.6 Do-while

D.7.7 Break

D.7.8 continue

D.7.9 return

D.8 The C Preprocessor

D.8.1 Macro substitution

D.8.2 File inclusion

D.9 Some Standard Library Functions

D.9.1 I/O Functions

D.9.2 String Functions

D.9.3 Math Functions

D.9.4 Utility Functions

E Useful Tables

E.1 Commonly Used Numerical Prefixes

E.2 Standard ASCII codes

E.3 Powers of 2

F Solutions to Selected Exercises